【动态规划专题】LeetCode 72. 编辑距离

本问题对应课程链接：剑指offer刷题第七期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 2 年前 80 3

共以下 3 个回答

陆狗陆狗普通 2025年1月3日上午9:41

解题思路
– dp成二维数组，dp[i][j],表示word1的i位的字字符串和word2的j位的子字符串最小编辑距离
– dp[i][j]如何从前序状态变更过来？
– 情形1：如果最后一个字符相同，那么dp[i][j]=dp[i-1][j-1]
– 情形2：如果最后一个字符不相同，还得分情况(那种方式最小就取哪种)
– 情形2.1：如果是可以替换过来，dp[i][j]=dp[i-1]dp[j-1]+1
– 情形2.2：如果是多余的字符，dp[i][j]=dp[i][j-1]+1
– 情形2.3：如果是缺少的字符，dp[i][j]=dp[i-1][j]+1
【题解1】

class Solution {
    public int minDistance(String word1, String word2) {
        // dp成二维数组，dp[i][j],表示word1的i位的字字符串和word2的j位的子字符串最小编辑距离
        // dp[i][j]如何从前序状态变更过来？
        // 情形1：如果最后一个字符相同，那么dp[i][j]=dp[i-1][j-1]
        // 情形2：如果最后一个字符不相同，还得分情况(那种方式最小就取哪种)
        // 情形2.1：如果是可以替换过来，dp[i][j]=dp[i-1]dp[j-1]+1
        // 情形2.2：如果是多余的字符，dp[i][j]=dp[i][j-1]+1
        // 情形2.3：如果是缺少的字符，dp[i][j]=dp[i-1][j]+1
        int m = word1.length();
        int n = word2.length();
        // 因为范围应该是[0,m]和[0,n]，其中0表示空字符串，也要占位
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        // 第1行
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        // 第1列
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char w1 = word1.charAt(i - 1);
                char w2 = word2.charAt(j - 1);
                if (w1 <span class="text-highlighted-inline" style="background-color: #fffd38;"> w2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 【错误】注意，三个数取最小值，只能2个数字进行min比较
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

错误点1：注意，三个数取最小值，只能2个数字进行min比较

0 赞同 0 条回复

秋山丽奈普通 2024年12月30日下午8:03

思路：递归处理

class Solution {
    public int minDistance(String word1, String word2) {

       char[] word1List = word1.toCharArray();
       char[] word2List = word2.toCharArray();

        int[][] ans = new int[word1List.length+1][word2List.length+1];

        for(int i = 0; i < word1List.length+1; i ++){
            // 从 word1[0...i] 转为word2[0]  需要 i 步 
            ans[i][0] = i;
        }

        for(int i = 0; i < word2List.length+1; i ++){
            // 从 word2[0...i] 转为word1[0]  需要 i 步 
            ans[0][i] = i;
        }

        for(int i = 1; i <= word1List.length; i ++){
            for(int j = 1; j <= word2List.length; j ++){
                if(word1List[i-1] == word2List[j-1]){
                    // 当前元素相同
                    ans[i][j] = 1+Math.min(ans[i-1][j-1]-1, Math.min(ans[i-1][j], ans[i][j-1]));
                }else{
                    ans[i][j] = 1+Math.min(ans[i-1][j-1], Math.min(ans[i-1][j], ans[i][j-1]));
                }
            }
        }

        return ans[word1List.length][word2List.length];


    }
}

0 赞同 0 条回复

Aatorx 永久会员 2024年12月27日下午3:49

class Solution {
public:
    int minDistance(string word1, string word2) {
        if(word1.empty() || word2.empty()) {
            return max(word1.size(), word2.size());
        }
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        for(int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(word1[i - 1] != word2[j - 1]){
                    dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }else{
                    dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
};

dp[i][j]表示从长度为i的word1变为长度为j的word2需要的最小步数。
时间复杂度O(Mn)，空间复杂度O(Mn)。

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【动态规划专题】LeetCode 72. 编辑距离

共以下 3 个回答

# 回答此问题 取消回复

# 回答此问题取消回复