algorithm - 字符串算法作业/面试类问题

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作为基础并扩展它以记住添加/删除/替换的字符。这将以线性时间运行。