string - 检查一个字符串是否是另外两个给定字符串的洗牌

Question

这是算法设计手册中的一道题:

Suppose you are given three strings of characters: X, Y, and Z, where |X| = n, |Y| = m, and |Z| = n+m. Z is said to be a shuffle of X and Y if and only if Z can be formed by interleaving the characters from X and Y in a way that maintains the left-to ­right ordering of the characters from each string.

Give an efficient dynamic ­programming algorithm that determines whether Z is a shuffle of X and Y.

Hint: the values of the dynamic programming matrix you construct should be Boolean, not numeric

这是我尝试过的:

最初，我做了一个一维的char数组，分别指向X,Y,Z的起始字符。如果 Z 指针与 X 指针匹配，则将 X 存储在 char 数组中，否则使用 Y 指针检查是否相同。如果 char 数组中的每个条目都与其最后一个条目不同，则 Z 不会交错。

谁能帮我解决这个问题？

Answer 1

首先，让我们从一些定义开始。我为 X 的第 i 元素写 X[i] ，为 X[i) 的子字符串写X 从索引 i 开始。

例如，如果 X = abcde，则 X[2] = c 和 X[2) = cde。

Y 和 Z 的定义类似。

---

要通过动态规划解决问题，您应该保留一个大小为 (n+1) x (m+1) 的二维 bool 数组 A。在这个数组中，A[i, j] = true 当且仅当 X[i) 和 Y[j) 可以交错为形成 Z[i+j)。

对于任意的(i, j)，在二维数组的中间某处，递推关系很简单:

A[i, j] := X[i] = Z[i+j] and A[i+1, j]
        or Y[j] = Z[i+j] and A[i, j+1]

在二维数组的边缘，X 或 Y 已经在其末尾，这意味着另一个的后缀应等于Z 的后缀:

A[m, j] := Y[j) = Z[m+j)
A[i, n] := X[i) = Z[i+n)
A[m, n] := true

---

如果先填充数组的边界(A[m, j]和A[i, n]，对于所有的i, j)，然后您可以简单地返回 A[0, 0] 并适本地设置条目。最后 A[0, 0] 就是你的答案。