LeetCode 0072. 编辑距离[动态规划详解]

原创

Yano_nankai

修改于 2021-03-05 14:29:21

4800

修改于 2021-03-05 14:29:21

文章被收录于专栏：二进制文集二进制文集

题目描述

题目链接

给你两个单词 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')

解题思路

定义 dpi 为 w10:i 和 w20:j 的编辑距离，则分为两种情况：

w1i == w2j，则这个字符不用编辑，dpi = dpi-1
w1i != w2j，则有三种情况：
- 删除 w1i，则 dpi = dpi-1 + 1
- 删除 w2j，则 dpi = dpi + 1
- 更改字符 w1i 或 w2j，则 dpi = dpi-1 + 1

代码

class Solution {
    public int minDistance(String w1, String w2) {
		int[][] dp = new int[w1.length() + 1][w2.length() + 1];
        for(int i = 0; i <= w1.length(); i++) {
            dp[i][0] = i;
        }
        for(int i = 0; i <= w2.length(); i++) {
            dp[0][i] = i;
        }
        
        for(int i = 1; i <= w1.length(); i++) {
           for(int j = 1; j <= w2.length(); j++) {
                if(w1.charAt(i - 1) == w2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 分别对应删、增、改
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            } 
        }
        
        return dp[w1.length()][w2.length()];
    }
}