1

假设我有一个长度为 N 的“目标字符串”（或列表，并不重要）。为简单起见，假设有两个且只有两个可能的字符，“A”和“B”。因此，例如，目标字符串可能是“ABBABB”。

然后给我一个长度为 <= N 的测试字符串（同样，两个可能的字符）。我想确定在唯一合法的转换是插入字符的约束下，测试字符串是否可以转换为目标字符串。

例如，再假设目标是 ABBABB，测试是 BBB。那么答案是肯定的，测试可以转化为目标；例如：BBB -> BBAB -> ABBAB -> ABBABB。

但是如果测试是 BABA，那么它就无法转换为目标，因为目标以 A 开头，测试不会，并且在测试中插入 A 将不起作用，因为这会导致它有更多的 A比目标有。

显然，我可以通过暴力破解所有可能的字符插入序列来做出这个是或否的决定。但是有没有更有效的方法？

提前致谢。

4

3 回答 3

7

乍一看，简单的答案似乎是如果测试字符串顺序包含在目标字符串中，那么您的测试就通过了。

就像是：

int i = 0;
foreach (char c in target) {
    if (i == test.Length) return true; // Found all test chars
    if (test[i] == c) {
        i++; // found this test char; check for next
        if (i == test.Length) break;
    }
}
return i == test.Length; // Found all test chars
于 2012-04-20T21:08:02.750 回答
1

您可以使用动态编程来解决这个问题。令 X 为初始字符串，Y 为最终字符串。让我们解决相反的问题，即从 Y 中删除，看看我们是否可以得到 X。

F(Y,X) = (if X[0]=Y[0]: F(X[1:],Y[1:] ) or F(Y[1:],X)

结束条件：If X='', return True elsif Y='' return False

请注意，与所有动态规划问题一样，您需要为 len(X)*len(Y) (i,j) 的不同组合计算并存储 F(X[i:],F[j:])。

于 2012-04-20T20:44:22.297 回答
0

1) 将测试/目标字符串转换为数组，其中每个元素是一对描述连接的“A”和“B”的数量。

例如 ABBABB ==> { (1,2) (1,2) }; BBB ==> { (0,3) }; 巴巴 ==> { (0,1) (1,1) (1,0) }

2）定义元素级别包含：如果a>=c且b>=d，则P1（a，b）包含P2（c，d）

在两个元素 P1 (a,b) 和 P2 (c,d) 上定义两个操作

合并A(P1,P2) ==> (a+c,d);

合并B(P1,P2) ==> (a,b+d)

3）现在我们有一个抽象的问题：给定测试数组{T1，T2，...，Tn}和目标数组{A1，A2，...Am}，指示目标数组是否包含测试数组。这里“包含”可以递归定义。

如果 i，目标数组包含测试数组。目标数组具有与测试数组相同或更多的元素；ii. 对于 [1,m] 中的每个 i，Ai 都包含 Ti

或者

mergeA(A1,A2), A3, A4 ... 包含测试数组

或者

mergeB(A1,A2), A3, A4 ... 包含测试数组

4) 伪代码

bool ifContain(Pair[] target, Pair[] test) {
    if (test.length>target.length) return false;
    if (test.length()==1) 
        return (target.A>=test.A && target.B>=test.B);
    return   (ifContain(target[0], test[0]) && ifContain(targe(1,:),test(1,:)))
        || ifContain(Pair(target[0].a,target[0].b+target[1].b)+target(2,:),test)
        || ifContain(Pair(target[0].a+target[1].a+target[1].b)+target(2,:),test);
}
于 2012-04-20T21:56:45.040 回答