LeetCode - Edit Distance

左手的ㄟ右手 2022-08-04 12:45 23阅读 0赞

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character  
b) Delete a character  
c) Replace a character

一个非常经典的动态规划问题，状态转移方程：

f(i-1, j-1) word1\[i\] == word2\[j\]

f(i, j) =

Min\{ f(i-1, j), f(i, j-1), f(i-1, j-1\} \} + 1 word1\[i\] != word2\[j\]

如上所示，f(i, j)表示word1.substring(i)与word2.substring(j)直接的距离

1）显然，如果word1\[i\] == word2\[j\]，转化为递归解，即f(i-1, j-1)

2）如果word1\[i\] == word2\[j\]，则可以对两个字符的最后一个字符串进行三种操作，对与字符word1\[i\]可以进行如下三种操作：

i) delete，即把此字符删除，则问题转化为f(i-1, j)

ii) replace，即把此字符替换为word2\[j\]，则问题转化为f(i-1, j-1)

iii) Insert，即在此处增加一个字符word2\[j\]， 则问题转化为f(i, j-1)

根据上述状态转移方程，很容易写出代码

public int minDistance(String word1, String word2) {
           if (word1.equals(word2)) {
                return 0;
            }
            if (word1.length() == 0 || word2.length() == 0) {
                return Math.abs(word1.length() - word2.length());
            }
            int[][] dp = new int[word1.length() + 1][word2.length() + 1];
            for (int i = 0; i <= word1.length(); i++) {
                dp[i][0] = i;
            }
            for (int i = 0; i <= word2.length(); i++) {
                dp[0][i] = i;
            }
            for (int i = 1; i <= word1.length(); i++) {
                for (int j = 1; j <= word2.length(); j++) {
                    if (word1.charAt(i - 1) == word2.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[word1.length()][word2.length()];
        }

又是一个比较经典的动态规划问题。