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

时间:2021-06-16 19:33:10

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

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

 

代码:

 1 class Solution {
 2     public int minDistance(String s1, String s2) {
 3         int[][]dp = new int[s2.length() + 1][s1.length() + 1];
 4         dp[0][0] = 0;
 5         for(int i = 1; i<=s2.length(); i++){
 6             dp[i][0] = i;
 7         }
 8         for(int j = 1; j<=s1.length(); j++){
 9             dp[0][j] = j;
10         }
11         for(int i = 1; i<=s2.length(); i++){
12             for(int j = 1; j<=s1.length(); j++){
13                 if( s1.charAt(j-1) ==  s2.charAt(i-1)  ){
14                     dp[i][j] = dp[i-1][j-1];
15                 }else{
16                     dp[i][j] =  Math.min(dp[i-1][j-1], Math.min(dp[i][j-1] , dp[i-1][j] ))  + 1 ;
17                 }
18             }      
19         }
20        return  dp[s2.length()][s1.length()];
21     }
22 }