[leetcode] 72. Edit Distance 最少编辑步数

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

 

You have the following 3 operations permitted on a word:

 

1. Insert a character
2. Delete a character
3. Replace a character

 

题意： 

给定两个串串： word1, word2;  找出word1变身成word2的最小步数的操作（仅限插入、删除和替换这三种操作）

 

思路：

动态规划的高频题，需要熟练掌握

字符串生成子序列或者字符串的匹配问题，要巴普诺夫条件反射想到dp

开一个2D array， dp[word1.length() + 1 ][ word2.length() + 1]

      word2 = 0  r o s

         0   0   

word1 =  h

         o

         r

         s

         e

 

 

用dp[i][j]来记录当前word1变身成word2的最小步数

1.    若word1.charAt(i-1) == word2.charAt(j-1) 【留心字符串的index和2D array的坐标有差，这里很容易误写成word1.charAt(i) == word2.charAt(j) 】

　　dp[i][j] = dp[i-1][j-1]   

　　即若当前word1串串和word2串串的当前字符相同，则不需要做任何convert操作，直接将之前dp[i-1][j-1] 结果拿过来

 

2.    若word1.charAt(i-1) == word2.charAt(j-1)

　　dp[i][j] = min( dp[i-1][j-1],  dp[i-1][j],  dp[i][j-1] )  + 1 

       即若当前word1串串和word2串串的当前字符不同， 则

       要么word1插入 word2当前的字符， dp[i][j] = dp[i][j-1] + 1  

　　要么word1删除 word1当前的字符， dp[i][j] = dp[i-1][j] + 1

       要么word1替换 word2当前的字符， dp[i][j] = dp[i-1][j-1] + 1

       取以上三个操作中最小的步数

 

代码：

class Solution {
    public int minDistance(String s1, String s2) {
        int[][]dp = new int[s2.length() + 1][s1.length() + 1];
        dp[0][0] = 0;
        for(int i = 1; i<=s2.length(); i++){
            dp[i][0] = i;
        }
        for(int j = 1; j<=s1.length(); j++){
            dp[0][j] = j;
        }
        for(int i = 1; i<=s2.length(); i++){
            for(int j = 1; j<=s1.length(); j++){
                if( s1.charAt(j-1) ==  s2.charAt(i-1)  ){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] =  Math.min(dp[i-1][j-1], Math.min(dp[i][j-1] , dp[i-1][j] ))  + 1 ;
                }
            }      
        }
       return  dp[s2.length()][s1.length()];
    }
}