算法: 最小步骤使两个字符串相等72. Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

动态规划解法

让以下成为函数定义：-

dp(i, j) := 将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小成本（或步骤）

• 情况 1：word1[i] == word2[j]，即第 j 个字符匹配。

dp(i + 1, j + 1) = dp(i, j)

• 情况 2：word1[i] != word2[j]，那么我们必须插入、删除或替换，以更便宜的为准

dp(i + 1, j + 1) = 1 + min(dp (i, j + 1), dp(i + 1, j), dp(i, j))

1. dp(i, j + 1) 表示插入操作
2. dp(i + 1, j) 表示删除操作
3. dp(i + 1, j + 1) 表示替换操作
   在这里，我们考虑从 word1 到 word2 的任何操作。这意味着，当我们说插入操作时，我们在 word1 之后插入一个与 word2 的第 j 个字符匹配的新字符。所以，现在必须将 word1 的 i 个字符匹配到 word2 的 j + 1 个字符。其他 2 个操作也是如此。

请注意，问题是对称的。一个方向的插入操作（即从word1到word2）与另一个方向的删除操作相同。所以，我们可以选择任何方向。

以上方程成为DP的递归定义。

基本情况：

dp(0, k) = dp(k, 0) = k

下面是这种循环关系的直接自下而上的翻译。使用实际代码处理基于 0 的索引很重要：

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (int r = 0; r <= len1; r++)
            dp[r][0] = r;
        for (int c = 0; c <= len2; c++)
            dp[0][c] = c;
        for (int r = 0; r < len1; r++) {
            for (int c = 0; c < len2; c++) {
                if (chars1[r] == chars2[c]) {
                    dp[r + 1][c + 1] = dp[r][c];
                } else {
                    dp[r + 1][c + 1] = Math.min(dp[r][c], Math.min(dp[r+1][c], dp[r][c+1])) + 1;
                }
            }
        }
        
        return dp[len1][len2];
    }
}

视频：https://www.youtube.com/watch?v=We3YDTzNXEk

参考

https://leetcode.com/problems/edit-distance/discuss/25849/Java-DP-solution-O(nm)