LeetCode 72.编辑距离

LeetCode 72.编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

思路：

f[i,j]表示a[1~i] 变成 b[1~j]需要的操作次数。
有一点我们需要注意的是，f[i,j]并不是把a[1~i] 变成了 b[1~j]。
共三种选择：

1. 删除 f[i-1,j] + 1 //比如 a = AEFG ,b=AEF，所以就是a[1~i-1]与b[1~j]匹配，这时候删除了 a[i]，就是 f[i-1,j] + 1，即a[1~i] 变成 b[1~j]需要的操作次数。
2. 增加 f[i,j-1] + 1 //比如 a=AEF,b=AEFG, a[1~i]已经与b[1~j-1]匹配，只要我们增加一个 b[j]到a数组中就可以完成匹配，就是a[1~i] 变成 b[1~j]的操作次数。
3. 修改f[i-1,j-1] + 1/0 //是否修改取决于a[i] == b[j]?

代码：

class Solution {
public:
    vector<vector<int>> f;

    int minDistance(string word1, string word2) {
        int n=word1.size();
        int m=word2.size();

        word1 = ' ' + word1;
        word2 = ' ' + word2;
        f = vector<vector<int>> (n + 1,vector<int> (m + 1));
        //把word1 删成 word2 有多长就删多少次
        for(int i=1;i<=n;i++) f[i][0]=i;
        //把word2 增加 word2 word2有多长就增加多少次
        for(int i=1;i<=m;i++) f[0][i]=i;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                //删除 增加
                f[i][j]=min(f[i-1][j] + 1 , f[i][j-1] + 1);
                //修改 如果不相等
                if(word1[i] != word2[j]) f[i][j]=min(f[i][j],f[i-1][j-1] + 1);
                else f[i][j]=min(f[i][j] , f[i-1][j-1]);
            }
        }
        return f[n][m];
    }
};