3

在准备期末考试时对动态编程问题进行了一些练习，我发现这个问题难倒了我。

拉链：给定三个字符串，你要确定第三个字符串是否可以由前两个字符串中的字符组合而成。前两个字符串可以任意混合，但每个字符串中的字符必须保持在第三个字符串中的原始顺序。

例如，考虑由“cat”和“tree”组成“tcarete”： 字符串 A：cat 字符串 B：树 字符串 C：tcarete

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

作为第二个例子，考虑由“cat”和“tree”组成“catrtee”： 字符串 A：cat 字符串 B：tree 字符串 C：catrtee

此输入的答案也是“是”

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

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

4

1 回答 1

4

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

现在，让我们这样想：

  1. 对于整个字符串 C，如果是 A 和 B 的混合，那么它的第一个字符必须是 A 的第一个字符，或者 B 的第一个字符；
  2. 现在更进一步，kC 中的第一个字符，其中的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。

于 2013-05-08T14:37:56.667 回答