本文共 4021 字，大约阅读时间需要 13 分钟。

原文地址：

已知两个字符串str1与str2，str1可以用下面的操作。得到最小的编辑数使得str1转变为str2。 a）insert b）remove c）replace 以上所有的操作成本是一样的。

例子：

Input:   str1 = "geek", str2 = "gesek"Output:  1我们可以通过在str1中插入一个‘s’转变为str2。Input:   str1 = "cat", str2 = "cut"Output:  1我们可以通过在str1中的‘a’替换为‘u’转变为str2。Input:   str1 = "sunday", str2 = "saturday"Output:  3最后三个字符和第一个字符相同。也就是将"un"替换为"atur"。所以可以用下面的三个步骤。用'r'替换'n', 插入t, 插入a。

这个例子的子问题又是啥玩意儿呢？

这个想法是从开始或者从两段逐个处理所有的字符。 我们从右边开始遍历，对于被遍历的每一对字符都有两种可能。

m: Length of str1 (first string)n: Length of str2 (second string)

如果两个字符串的最后一个字符相同，那就啥也不用干。忽略最后一个字符，继续处理剩下的字符串，所以递归长度为m-1与n-1。

否则（如果最后一个字符不相同），我们要考虑在str1上的所有操作，考虑在第一个字符串的最后一个字符上的三种操作，递归地计算三种操作的最小代价以及三个值得最小值。

• insert：递归m与n-1；
• remove：递归m-1与n；
• replace：递归m-1与n-1；

下面是上述简单的C++递归实现：

// A Naive recursive C++ program to find minimum number// operations to convert str1 to str2#include
   
    using namespace std;// Utility function to find minimum of three numbersint min(int x, int y, int z){   return min(min(x, y), z);}int editDist(string str1 , string str2 , int m ,int n){    // If first string is empty, the only option is to    // insert all characters of second string into first    if (m == 0) return n;    // If second string is empty, the only option is to    // remove all characters of first string    if (n == 0) return m;    // If last characters of two strings are same, nothing    // much to do. Ignore last characters and get count for    // remaining strings.    if (str1[m-1] == str2[n-1])        return editDist(str1, str2, m-1, n-1);    // If last characters are not same, consider all three    // operations on last character of first string, recursively    // compute minimum cost for all three operations and take    // minimum of three values.    return 1 + min ( editDist(str1,  str2, m, n-1),    // Insert                     editDist(str1,  str2, m-1, n),   // Remove                     editDist(str1,  str2, m-1, n-1) // Replace                   );}// Driver programint main(){    // your code goes here    string str1 = "sunday";    string str2 = "saturday";    cout << editDist( str1 , str2 , str1.length(), str2.length());    return 0;}
   

输出：

3

上面的方法时间复杂度是指数级的，在最差的情况下需要O(3^m)次操作。只有在两个字符串没有一个字符能皮配得上的时候，才是最坏的情况。下图是最坏情况的递归调用：

我们可以看到有许多的子问题一次又一次地计算，例如eD(2,2)就被计算了三次。因为相同的子问题重复调用，所以这个问题有重复子问题的属性。所以编辑距离问题具有动态规划问题的两个属性。就行其他典型的DP问题一样，可以通过构建临时数组存储子问题答案来避免相同的子问题重新计算。

// A Dynamic Programming based C++ program to find minimum// number operations to convert str1 to str2#include
   
    using namespace std;// Utility function to find minimum of three numbersint min(int x, int y, int z){    return min(min(x, y), z);}int editDistDP(string str1, string str2, int m, int n){    // Create a table to store results of subproblems    int dp[m+1][n+1];    // Fill d[][] in bottom up manner    for (int i=0; i<=m; i++)    {        for (int j=0; j<=n; j++)        {            // If first string is empty, only option is to            // isnert all characters of second string            if (i==0)                dp[i][j] = j;  // Min. operations = j            // If second string is empty, only option is to            // remove all characters of second string            else if (j==0)                dp[i][j] = i; // Min. operations = i            // If last characters are same, ignore last char            // and recur for remaining string            else if (str1[i-1] == str2[j-1])                dp[i][j] = dp[i-1][j-1];            // If last character are different, consider all            // possibilities and find minimum            else                dp[i][j] = 1 + min(dp[i][j-1],  // Insert                                   dp[i-1][j],  // Remove                                   dp[i-1][j-1]); // Replace        }    }    return dp[m][n];}// Driver programint main(){    // your code goes here    string str1 = "sunday";    string str2 = "saturday";    cout << editDistDP(str1, str2, str1.length(), str2.length());    return 0;}
   

输出：

3

时间复杂度：O(m x n)

附加空间：O(m x n)

应用场景：编辑距离算法有许多实际的应用，参考Lucene API 样本。另外的一个例子是显示词典中的所有单词，这个单词邻近一个已知或者错误拼写的单词。