字符串算法作业/类似面试的问题

Question

假设我们必须使用字符串A和B。任务是在字符串B中插入任何所需的字母，以便以字符串A结束。

例如：

A - This is just a simple test 
B - is t a sim te

所以如果我们这样看字符串A：

--is -- ---t a sim--- te--

或者：

---- is ---t a sim--- te--

很明显，我们可以从字符串B构建字符串A，并且输出应该是上面所写的格式(两个答案都是正确的)。

你能想出一个算法在合理的时间内解决这个问题吗？想出暴力解决方案很容易，但我需要比这更复杂的东西。

Answer 1

您可以将Levenshtein distance algorithm作为基础，并对其进行扩展，以记住添加/删除/替换的字符。这将在线性时间内运行。

Answer 2

您可以在A中查找B的字符的第一个匹配项，只需在A中找到最后一个索引之后开始查找匹配项，例如在您的示例中：

A - This is just a simple test 
B - is t a sim te

i: 3rd place in A,
s: 4th place in A,
' ': 5th place in A,
t: 12th place in A, (because last index was 4)
' ': ...
a: ....

这是O(|A|+|B|)，因为|A| > |B|是O(|A|)。

在找到索引后，很容易将B转换为A，只需将两个索引之间的A字符添加到B即可。

编辑：如果没有匹配该算法，也可以正常工作(B中将有一些字符不在A中，从上一个索引开始)。

Answer 3

我想你可以用一个很好的reg表达式来确定它是否可行。因为在B中建议的任何字符之间可能有也可能没有1个或更多个字符。