编辑距离算法，用于查找将一个字符串转换为另一个字符串的最小操作

Question

让我们举个例子，str1="ABC"，str2="AFB"为了找到最低步骤，我们考虑了三种可能性-（因为字符串的最后一个字母不匹配）

1) 1+f("ABC","AF")
2) 1+f("AB","AFB")
3) 1+f("AB","AF")

并至少采取三个..我的疑问是，我们为什么不考虑1+f（"ABC"，"AB"）请解释一般情况，而不是这个。谢谢。

Answer 1

确实还有更多的可能性。但是算法不需要立即考虑它们。

计算距离的方法是通过提出一些问题并枚举答案来将其减少到较小的任务。

在您的情况下，问题可能是：最佳编辑顺序将如何使最后个字符相等？

有 3 个可能的答案：

1. 它将从ABC中删除C，然后我们得到子问题(AB,AFB)
2. 它会ABC增加B，然后我们得到子问题(ABCB,AFB)
，相当于(ABC,AF)
3. 它将C替换为B，然后我们得到子问题(ABB,AFB)
，相当于(AB,AF)

当然，从这些选项中，我们选择最短的答案。

当然

可以提出不同的问题，但主要思想是，我们希望要求一些较小的信息，以将问题简化为一系列（或树）子问题。