通过插入字符确定是否可以将一个字符串更改为另一个字符串的算法？

Question

假设我有一个长度为N的"目标字符串"(或列表,并不重要).为简单起见,假设有两个且只有两个可能的字符,"A"和"B".因此,例如,目标字符串可能是"ABBABB".

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

例如,让我们再次说目标是ABBABB,测试是BBB.然后答案是肯定的,测试可以转化为目标; 例如:BBB - > BBAB - > ABBAB - > ABBABB.

但是如果测试是BABA,则它无法转换为目标,因为目标以A开头,测试没有,并且在测试中插入A将无法工作,因为这将导致它有更多的A比目标有.

显然,我可以通过蛮力,通过所有可能的字符插入序列来做出这个是或否决定.但是有更有效的方法吗？

提前致谢.

Answer 1

乍一看,简单的答案似乎是测试字符串是否按顺序包含在目标字符串中然后测试通过.

就像是:

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