leetcode72. 编辑距离

分析

与acwing同源，只是要注意下标问题，f[i][j]和word[i],word[j]要对齐

class Solution {
public:
    int minDistance(string word1, string word2) {
        int la=word1.length(),lb=word2.length();
        word1=" "+word1;
        word2=" "+word2;//或者后面word1[i-1]!=word2[j-1]
        int f[la+1][lb+1];//f[i][j]表示由word1[i]->word2[j]的最少步骤
        for(int i=0;i<=lb;i++)f[0][i]=i;
        for(int i=0;i<=la;i++)f[i][0]=i;
        for(int i=1;i<=la;i++){
            for(int j=1;j<=lb;j++){
                f[i][j]=min(f[i-1][j],f[i][j-1])+1;//word1和word2长度不同，进行增加或者删除
                f[i][j]=min(f[i][j],f[i-1][j-1]+(word1[i]!=word2[j]));//长度相同，最后一个字母不同或者相同
            }
        }
        return f[la][lb];
    }
};