假设我们需要字符串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，并且输出应该是上述的书面格式（两个答案都是正确的）。
你能想出一个在合理时间内解决这个问题的算法吗很容易想出蛮力解决方案，但我需要比这更复杂的东西。
最佳答案
您可以将Levenshtein distance algorithm作为基数，并对其进行扩展，以记住添加/删除/替换的字符这将在线性时间内运行。