假设我有一个长度为N的"目标字符串"(或列表,并不重要).为简单起见,假设有两个且只有两个可能的字符,"A"和"B".因此,例如,目标字符串可能是"ABBABB".
然后给我一个长度<= N的测试字符串(同样,两个可能的字符相同).我想确定在唯一合法转换是插入字符的约束下,是否可以将测试字符串转换为目标字符串.
例如,让我们再次说目标是ABBABB,测试是BBB.然后答案是肯定的,测试可以转化为目标; 例如:BBB - > BBAB - > ABBAB - > ABBABB.
但是如果测试是BABA,则它无法转换为目标,因为目标以A开头,测试没有,并且在测试中插入A将无法工作,因为这将导致它有更多的A比目标有.
显然,我可以通过蛮力,通过所有可能的字符插入序列来做出这个是或否决定.但是有更有效的方法吗？
提前致谢.