如何使用递归和记忆来了解一个字符串是否是其他两个字符串的组合？

Question

考虑 2 个字符串：

a = "wxy"
b = "mnop"
z = "wmxnoyp"

字符串 z 是一个混合字符串，如果它是字符串 a 和 b 的组合，使得字符串 z 的长度等于字符串 a 和 b 的长度之和，并且字符串 a 和 b 中没有一个字母重复。另请注意，每个字符均按字符串 a 和 b 的递增顺序排列。例如，如果

a = "tuim"
b = "oprn"
z = "moiprunt" 

z 不是混合字符串，因为即使 z 的长度等于字符串 a 和 b 的长度之和，字符串 z 也不是字符串 a 和 b 的递增顺序。

如果 z 是 a 和 b 的混合字符串，我希望我的代码返回 true，如果字符串 z 不是 a 和 b 的混合字符串，则返回 false。

如何使用递归和记忆编写代码？我知道我将要求我的代码使用二维数组来存储已计算的值（作为表格），但是，我不明白表格的 x 和 y 轴应代表什么以及我的代码应如何表示填写该表中的值。

如果有人可以通过示例简要解释表格应该是什么样子，那就太好了。

Answer 1

这个问题不需要动态规划。可以用贪心算法来解决。我们可以迭代

z

字符串并查看相应的字符是否与

a

或

b

中的第一个字符匹配。如果没有，那么就没有成功。如果存在匹配，则重复

z

中的下一个字符，但现在丢弃

a

或

b

中已匹配的字符，...等等。

它的外观如下（Python）：

def is_combination(a, b, z):
    i = 0
    j = 0
    for ch in z:
        if i < len(a) and ch == a[i]:
            i += 1
        elif j < len(b) and ch == b[j]:
            j += 1
        else:
            return False
    return i == len(a) and j == len(b)