Leetcode 72. 编辑距离

叁歲伎倆 2022-09-02 13:55 113阅读 0赞

#### 题目重述 ####

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/edit-distance  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

#### Java实现 ####

class Solution {
        
        public int minDistance(String word1, String word2) {
        
            // 如果两字符串相等，则不需要变换
            if (word1.equals(word2)) {
        
                return 0;
            }
            // 若一个为空字符串
            if(word1.length()*word2.length()==0)
            {
        
                return word1.length()+word2.length();
            }
            // dp表,dp[i][j]代表 字符串1的前i个字符变换到字符串2的前j个字符 所需要的最小编辑距离
            int[][] dp = new int[word1.length() + 1][word2.length() + 1];
            for (int i = 0; i <= word1.length(); i++) {
        
                dp[i][0] = i;
            }
            for (int j = 0; j <= word2.length(); j++) {
        
                dp[0][j] = j;
            }
            // 动态转移方程
            for (int i = 1; i <= word1.length(); i++) {
        
                for (int j = 1; j <= word2.length(); j++) {
        
                   // 格外需要注意这里，dp[i][j]代表前i和前j，但对于字符串来说，第i个字符对应的下标是i-1
                    if (word1.charAt(i-1) == word2.charAt(j-1)) {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                    // 需要+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()];
        }
    }