[LeetCode]72. 编辑距离

DP，但要注意边界条件。
f[i][j]表示把word1的前i个字符转换成word2的前j个字符需要的最少操作数。

• word1[i-1]==word2[j-1]
  f[i][j]=min{f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]}
• word1[i-1]!=word2[j-1]
  f[i][j]=min{f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1}

72. 编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m=word1.size();
        int n=word2.size();
        int f[m+5][n+5];
        for (int i=0;i<=m;i++)
            for (int j=0;j<=n;j++) f[i][j]=1e9;
        //for (int i=0;i<=m;i++) f[i][0]=0;
        //初始化
        f[0][0]=0;
        
        for (int i=0;i<=m;i++)
            for (int j=0;j<=n;j++){
                if (j>0 && i>0){
                    //无需任何操作即可匹配
                    if (word1[i-1]==word2[j-1]) f[i][j]=min(f[i-1][j-1],f[i][j]);
                    //替换一个字符
                    if (word1[i-1]!=word2[j-1]) f[i][j]=min(f[i-1][j-1]+1,f[i][j]);
                }
                if (j>0){
                    //插入一个字符
                    f[i][j]=min(f[i][j-1]+1,f[i][j]);   
                }
                if (i>0){
                    //删除一个字符
                    f[i][j]=min(f[i-1][j]+1,f[i][j]);   
                }
            }
        if (m==0 || n==0) return max(m,n);
        return f[m][n];
    }
};