题目链接

LeetCode

题目描述

给你两个单词 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 由小写英文字母组成

    解题思路

    方法一：递归（超时）

    image.png
    image.png
    image.png
    image.png
    image.png
  1. class Solution {
  2. public:
  3.     int minDistance(string word1, string word2) {
  4.         if(word1.length()==0||word2.length()==0){
  5.             return max(word1.length(),word2.length());
  6.         }
  7.         if(word1.back()==word2.back()){
  8.             return minDistance(word1.substr(0,word1.length()-1),word2.substr(0,word2.length()-1));
  9.         }
  10.         return 1 + min(minDistance(word1.substr(0,word1.length()-1),word2.substr(0,word2.length()-1)),
  11.                 min(minDistance(word1,word2.substr(0,word2.length()-1)),
  12.                     minDistance(word1.substr(0,word1.length()-1),word2)
  13.                 ));
  14.     }
  15. };

方法二：动态规划

image.png

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();
        // 有一个字符串为空串
        if(m*n == 0){
            return n+m;
        }
        // DP 数组
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        // 边界状态初始化   当一个长度为0时，取长度最大值
        for(int i = 0;i<n+1;i++){
            dp[i][0] = i;
        }
        for(int i = 0;i<m+1;i++){
            dp[0][i] = i;
        }
        // 计算所有 DP 值
        for(int i=1;i<n+1;i++){
            for(int j = 1;j<m+1;j++){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = 1+min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]));
                }
            }
        }
        return dp[n][m];
    }
};

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if(m * n == 0){
            return m + n;
        }
        int[][] op = new int[m + 1][n + 1];
        for(int i = 0; i <= m; ++i){
            op[i][0] = i;
        }
        for(int i = 0; i <= n; ++i){
            op[0][i] = i;
        }
        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    op[i][j] = op[i-1][j-1];
                }else{
                    // op[i-1][j] 为 word1前i-1， word2前j最短编辑距离，也就是删除word1 i处
                    // op[i][j-1] 为 word1前i， word2前j-1最短编辑距离，也就是增加word1 i处
                    // op[i-1][j-1] 为 word1前i-1， word2前j-1最短编辑距离，也就是替换word1 i处和word2 j处相同
                    op[i][j] = 1 + Math.min(op[i-1][j], Math.min(op[i][j-1], op[i-1][j-1]));
                }
            }
        }
        return op[m][n];
    }
}
  • 时间复杂度 O(mn) m为word1的长度,n为word2的长度
  • 空间复杂度 O(mn)