LeetCode：72. 编辑距离

问题描述（原题链接）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少 *** 作数。
你可以对一个单词进行如下三种 *** 作：

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

代码： 第一个版本，通过91%

class Solution {
    public int minDistance(String word1, String word2) {
        //dp
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1][len2];
        if(len1==0 || len2==0)
        return len1==0?len2:len1;
        if(word1.charAt(0)==word2.charAt(0))
        dp[0][0]=0;
        else
        dp[0][0]=1;
        for(int i=1;i<len1;i++){
            dp[i][0]=dp[i-1][0]+1;//插入一个数即可
        }
        for(int i=1;i<len2;i++){
            dp[0][i]=dp[0][i-1]+1;
        }
        for(int i=1;i<len1;i++)
        for(int j=1;j<len2;j++){
            char c1=word1.charAt(i);
            char c2 = word2.charAt(j);
            if(c1==c2){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;  //删除,插入，替换一个
            }
        }
        return dp[len1-1][len2-1];
    }
}

第二个版本，通过100%

class Solution {
    public int minDistance(String word1, String word2) {
        //dp
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            dp[i][0]=dp[i-1][0]+1;//插入一个数即可
        }
        for(int i=1;i<=len2;i++){
            dp[0][i]=dp[0][i-1]+1;
        }
        for(int i=1;i<=len1;i++)
        for(int j=1;j<=len2;j++){
            char c1=word1.charAt(i-1);
            char c2 = word2.charAt(j-1);
            if(c1==c2){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;  //删除,插入，替换一个
            }
        }
        return dp[len1][len2];
    }
}