算法机考模拟题1006.单词变换

Description

对于两个只含有小写英文字母（’a’-‘z’）的单词word1和word2，你可以对word1进行以下3种操作：

 

1） 插入一个字母；

2） 删除一个字母；

3） 替换一个字母.

 

请计算将word1变换成word2的最少操作数.

 

word1和word2的长度均不大于1000.

 

请为下面的Solution类实现解决上述问题的函数minDistance，函数的参数word1和word2为给出的两个单词，返回值为所求最少操作数.

 

class Solution {

public:

    int minDistance(string word1, string word2) {

       

       }

};

 

例1：word1 = “sunny”, word2 = “snowy”，返回值为3.

 

例2：word1 = “abc”, word2 = “ac”，返回值为1.

 

 

注意：你只需要提交Solution类的代码，你在本地可以编写main函数测试程序，但不需要提交main函数的代码. 注意不要修改类和函数的名称.

设需要计算编辑距离的两个字符串分别为x[1...m]与y[1...n]

用E[i][j]表示x[1...i]与y[1...j]的编辑距离，则可以得到动态规划的状态转移方程：

当i=0时，E[i][j]=j；

当j=0时，E[i][j]=i；

当i>0且j>0时，E[i][j]=min{1+E[i-1][j],1+E[i][j-1],diff(i,j)+E[i-1][j-1]}

其中当x[i]=y[j]时，diff(i,j)=0;否则diff(i,j)=1.

class Solution {

public: int minx(int a,int b,int c){ int minNum = a; if(b<minNum){ minNum = b; } if(c<minNum) { minNum = c; } return minNum; } int minDistance(string word1, string word2) { int E[1001][1001]; for(int i=0; i <=word1.length(); i++){ E[i][0] = i; } for(int i=0; i <=word2.length(); i++){ E[0][i] = i; } for(int i=1; i <=word1.length(); i++){ for(int j=1; j <=word2.length(); j++){ if(word1[i-1]==word2[j-1]){ E[i][j] = minx(E[i][j-1]+1, E[i-1][j]+1, E[i-1][j-1]); } else { E[i][j] = minx(E[i][j-1]+1, E[i-1][j]+1, E[i-1][j-1]+1); } } } return E[word1.length()][word2.length()]; }};

状态数：mn

算法复杂度：O(1)

总复杂度：O(mn)