首先介绍一下概念

字符串编辑距离(Edit Distance),是俄罗斯科学家 Vladimir Levenshtein在1965年提出的概念,又称 Levenshtein距离,是指两个字符串之间,由一个转成另 一个所需的最少编辑操作次数。许可的编辑操作包括

1、将一个字符替换成另一个字符

2、插入一个字符

3、删除一个字符

可以借鉴LCS的思想，采用动态规划，维护一个c[m][n]二维数组，m,n的值分别为字符串1的长度+1，字符串2的长度+1。

c[0][0]表示的是二空串的编辑距离，明显为0。

c[1][0]表示的是字符串1的第一个字母和字符串2（空串）的编辑距离。

说明此二维数组的元素是二者字符串m和n位之间的编辑距离。

我们要求两字符串最小编辑距离，就是要使得c[m-1][n-1]最小。

其状态转换方程与LCS的类似，只是换成了求最小的值。

代码如下：

1 #include 
        
                                                                                                                          2   3 using namespace std;  4   5 int min(int num1, int num2, int num3)  6 {  7     return (num1 < num2 ? (num1 < num3 ? num1 : num3) : (num2 < num3 ? num2 : num3));  8 }  9  10 int EditLength(string str1, string str2) 11 { 12     int m = str1.size() + 1; 13     int n = str2.size() + 1; 14     int c[m][n]; 15     for(int i = 0; i < m; ++i) 16     { 17         c[i][0] = i; 18     } 19     for(int i = 0; i < n; ++i) 20     { 21         c[0][i] = i; 22     } 23     for(int i = 1; i < m; ++i) 24     { 25         for(int j = 1; j < n; ++j) 26         { 27             if(str1[i - 1] == str2[j - 1]) 28             { 29                 c[i][j] = c[i - 1][j - 1]; 30             }else 31             { 32                 c[i][j] = min(c[i-1][j-1], c[i-1][j], c[i][j-1]) + 1; 33             } 34         } 35     } 36     return c[m - 1][n - 1]; 37 } 38  39 int main(int argc, const char *argv[]) 40 { 41     string str1 = "iphone"; 42     string str2 = "iohonrt"; 43     int min = EditLength(str1, str2); 44     cout << min << endl; 45     return 0; 46 }
        

通过测试用例可得为3,结果正确。