Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character

问题：

给定两个字符串 A和B，由A转成B所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如将A(kitten)转成B(sitting)：

sitten （k→s）替换

sittin （e→i）替换

sitting （→g）插入

思路：

如果我们用 i 表示当前字符串 A 的下标，j 表示当前字符串 B 的下标。 如果我们用d[i, j] 来表示A[1, ... , i] B[1, ... , j] 之间的最少编辑操作数。那么我们会有以下发现：

1. d[0, j] = j;

2. d[i, 0] = i;

3. d[i, j] = d[i-1, j - 1] if A[i] == B[j]

4. d[i, j] = min(d[i-1, j - 1], d[i, j - 1], d[i-1, j]) + 1  if A[i] != B[j]

所以，要找出最小编辑操作数，只需要从底自上判断就可以了。

class Solution {public:    int minDistance(string word1, string word2) {        int m=word1.size();        int n=word2.size();        if(m==0)return n;        if(n==0)return m;        vector
     
       vec(n+1,INT_MAX);        vector
      
       
        > d(m+1,vec);        for(int ii=0;ii<=m;ii++)d[ii][0]=ii;        for(int jj=0;jj<=n;jj++)d[0][jj]=jj;        for(int i=1;i<=m;i++)        {            for(int j=1;j<=n;j++)            {                if(word1[i-1]==word2[j-1])d[i][j]=d[i-1][j-1];                else                {                    d[i][j]=min(d[i-1][j-1]+1,min(d[i-1][j]+1,d[i][j-1]+1));                }            }        }        return d[m][n];    }};
       
      
     

 

此题与类似