描述

給定兩個(gè)字符串 str1 和 str2 ，請(qǐng)你算出將 str1 轉(zhuǎn)為 str2 的最少操作數(shù)。
你可以對(duì)字符串進(jìn)行3種操作：
1.插入一個(gè)字符
2.刪除一個(gè)字符
3.修改一個(gè)字符。

image.png

思路：
1、初始條件： 假設(shè)第二個(gè)字符串為空，那很明顯第一個(gè)字符串子串每增加一個(gè)字符，編輯距離就加1，這步操作是刪除；同理，假設(shè)第一個(gè)字符串為空，那第二個(gè)字符串每增加一個(gè)字符，編劇距離就加1，這步操作是添加。 dp[i][0] 和 dp[0][j] 初始化從1開(kāi)始

2、如果str1 i位置對(duì)應(yīng) str2 j位置相等字符，那么操作次數(shù)與兩個(gè)子串的前一個(gè)相同dp[i][j] = dp[i-1][j-1]；
如果不相等， dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;

 public int editDistance (String str1, String str2) {
        // write code here
        int length1 = str1.length();
        int length2 = str2.length();
        int[][] dp = new int[length1+1][length2+1];
        for(int i = 1;i<=length1;i++){
            dp[i][0] = dp[i-1][0]+1;
        }
        for(int i = 1;i<=length2;i++){
            dp[0][i] = dp[0][i-1]+1;
        }
        for(int i = 1;i<=length1;i++){
             for(int j = 1;j<=length2;j++){
                 if(str1.charAt(i-1) == str2.charAt(j-1)){
                     dp[i][j] = dp[i-1][j-1];
                 }else{
    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                 }
                     
             }
        }
        return dp[length1][length2];
    }