LeetCode刷题系列 -- 72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符 删除一个字符 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 h 替换为 r) rorse -> rose (删除 r) rose -> ros (删除 e) 示例 2：

输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 t) inention -> enention (将 i 替换为 e) enention -> exention (将 n 替换为 x) exention -> exection (将 n 替换为 c) exection -> execution (插入 u)

提示：

0 <= word1.length, word2.length <= 500 word1 和 word2 由小写英文字母组成

思路：

1. 定义二维数组 dp[word1.length+1][word2.length+1] ，dp[i][j] 代表 word1 下标从 0,...,i-1 的子字符串变成 word2 [0,...,j-1] 的子字符串 的最小操作数 2. 初始化 dp[0][...] 与 dp[...][0]，dp[0][j] = j 表示 "" 变成 word2 [0,...,j] 字符串需要的最少操作数; dp[i][0] = i 表示 word1 变成 "" 需要的最小操作数; 3. 状态转移方程: 3.1) 若是 word1[i] == word2[j] ，则 dp[i][j] = dp[i-1][j-1] ，两个字符相等，操作数为 0 3.2）若是 word1[i] != word2[j], dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1]+1,dp[i-1][j-1]+1) 注：dp[i][j] = dp[i-1][j] + 1 表示 word1[0,...,i-2] 删除一个字符可以与 word2[0,...,j-1] 相同，操作加 1；（对word1[0,i-2]的操作就可以得到word2[0,j-1]，故只需要删除word1[i-1]字符即可） dp[i][j] = dp[i][j-1] + 1 表示 word1[0,...,i-1] 插入一个字符可以与 word2[0,...,j-1] 相同，操作加 1；（对word1[0,i-1]的操作就可以得到word2[0,j-2]，故只需要插入一个字符与 word2[j-1]匹配即可） dp[i][j] = dp[i-1][j-1] + 1 表示 word1[0,...,i-1] 4. 更新二维数组，dp[word1.length][word2.length] ，即为题目所求

java代码：

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        // 1 初始化
        // 表示 word1 [0,...,i] 变成 "" 需要的最小操作数
        for (int i = 0; i < word1.length() + 1; i++) {
            dp[i][0] = i;
        }
        // 表示 "" 变成 word2 [0,...,j] 字符串需要的最少操作数
        for (int j = 0; j < word2.length() + 1; j++) {
            dp[0][j] = j;
        }

        // 2 更新二维数组
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                // word1[i-1] == word2[j-2]，证明不需要任何操作
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = getMinNum(dp[i-1][j] + 1,dp[i][j-1]+1,dp[i-1][j-1]+1);
                }            }
        }
        return dp[word1.length()][word2.length()];
    }
    
    public int getMinNum(int a,int b,int c){
        return Math.min(a,Math.min(b,c));
    }
}