algorithm - 动态规划 : The Zipper

Question

在为期末考试做一些动态规划问题的练习时，我发现这个问题难倒了我。

Zippers:给定三个字符串，你要判断是否可以将前两个字符串中的字符组合成第三个字符串。前两个字符串可以任意混合，但每个字符在第三个字符串中必须保持原顺序。

例如，考虑从“cat”和“tree”组成“tcarete”:字符串 A:c a t字符串 B:t r e字符串 C:t c a r e t e

如您所见，我们可以通过选择“tree”的第一个字符，然后是“cat”的前两个字符，然后是“tree”的第二个和第三个字符，然后是最后一个字符来形成字符串 C分别为“猫”和“树”的字符。

作为第二个例子，考虑从“cat”和“tree”形成“catrtee”:字符串 A:c a t字符串 B:t r e字符串 C: c a t r t e e

这个输入的答案也是'是'

输出:如果 A 和 B 可以组合(压缩)成字符串 C，则输出 yes。 如果 A 和 B 不能组合成 C，则输出 no。

所以基本上我们想看看第三个字符串 C 是否可以由 A 和 B 组成。就像是C T R T E A E 会输出 No.我最大的问题是 cat 和 tree 中都有字母 T。所以我不能只运行一种算法来检查一个字母是否在另一个字母之后。有什么帮助吗？

Answer 1

因为你正在复习动态规划，所以用它来解决这个问题应该是很自然的。

现在，让我们这样想:

1. 对于整个字符串C，如果它是A和B的混合，那么它的第一个字符要么是A的第一个字符，要么是B的第一个字符；
2. 现在更进一步，C中的前k个字符，kA<k必须来自A，kB = k - kA 必须来自 B.

由此不难找出一个算法，使用O(min(len(A), len(B)))空间，使用O(len(C) * min(len(A), len (B))) 运行。

提示:对于通过 C 的每一步，A 中的某些位置必须为“开”，而其他位置则为“关”。最后，如果两个字符串中的所有字符都被消耗掉，则可以从A和B生成C。