题解 | #编辑距离(一)#

其实容易发现具有最优子结构，但状态以及状态的转换不好想。因为是两个字符串，所以定义dp[i][j]为s1的前i个s2的前j个的最短编辑距离。发现最后一步的不同点在于字符串不同时对字符串的操作，插入，删除或修改，对s1最后插入和删除s2最后是一样的效果，所以最后可以归纳为3中操作：

1. 在s1最后插入和s2最后一个字符相同的字符
2. 在s2最后插入和s1最后一个字符相同的字符
3. 替换s1最后和s2不同的字符

操作1：转化为dp[i][j-1]，即判断s1的前i个s2的前j-1个字符的最短编辑距离，无需考虑s2的第j个字符(因为会在s1的末尾插入)

操作2：转化为dp[i-1][j]

操作3：转化为dp[i-1][j-1]

最后得到状态的转化：

若 A 和 B 的最后一个字母相同：
D[i][j]
=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1]−1)
 
若 A 和 B 的最后一个字母不同：
D[i][j]=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1])

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        if(str1==null||str2==null||str1.length()==0||str2.length()==0){
            return 0;
        }
        int len1=str1.length();
        int len2=str2.length();
        char[] ss=str2.toCharArray();
        int[][] dp=new int[len1+1][len2+1];
        
        for(int i=1;i<=len1;i++){
            dp[i][0]=i;
            char c=str1.charAt(i-1);
            for(int j=1;j<=len2;j++){
                dp[0][j]=j;
                if(c==ss[j-1]){
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]-1)+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];    
        
        
    }
}