【动态规划专题】LeetCode 72. 编辑距离-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月19日下午7:53

class Solution {
    public int minDistance(String word1, String word2) {
        //二维动态规划数组
        int l1 = word1.length();
        int l2 = word2.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        for(int i = 1; i <= l1; i++) dp[i][0] = i;
        for(int j = 1; j <= l2; j++) dp[0][j] = j;
        for(int i = 1; i <= l1; i++){
            for(int j = 1; j <= l2; j++){
                //注意数组含义 dp[i][j] 比对的是字符串中i - 1 j - 1位置的元素
                if(word1.charAt(i - 1) == word2.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[l1][l2];
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月19日下午11:26

二维DP 和字符串DP的典型题

class Solution {
    public int minDistance(String word1, String word2) {
        char[] c1 = ("." + word1).toCharArray();
        char[] c2 = ("." + word2).toCharArray();
        int n2 = c2.length - 1;
        int n1 = c1.length - 1;

        int[][] f = new int[n1+1][n2+1];
        for (int i = 0; i <= n1; i++) f[i][0] = i;
        for (int i = 0; i <= n2; i++) f[0][i] = i;

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (c1[i] == c2[j]) f[i][j] = f[i-1][j-1];
                else {
                    f[i][j] = Math.min(
                        f[i-1][j],
                        Math.min(f[i][j-1], f[i-1][j-1])
                    ) + 1;
                }
            }
        }
        return f[n1][n2];
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月30日下午11:31

/**
时间空间复杂度O(MN) 为两个字符串长度的乘积
dp[i][j]:下标为i-1的word1和下标为j-1的word2，对应的编辑距离为dp[i][j]
递推公式：
word[i-1]==word2[j-1]时，不需要编辑dp[i][j] = dp[i-1][j-1]
不等时
1.删除word1[i-1],dp[i][j] = dp[i-1][j] + 1
2.删除word2[j-1] dp[i][j] = dp[i][j-1] + 1
3.替换：dp[i][j] = dp[i-1][j-1] + 1
 初始化
dp[i][0]：需要i次
dp[0][i]：需要i次
 */
class Solution {
    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        for(int i = 1;i <= l1;i++) {
            dp[i][0] = i;
        }
        for(int i = 1;i <= l2;i++) {
            dp[0][i] = i;
        }
        for(int i = 1;i <= l1;i++) {
            for(int j = 1;j <= l2;j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1])) + 1;
                }
            }
        }
        return dp[l1][l2];
    }
}

0 赞同 0 条回复

Mooby 普通 2022年11月30日下午8:57

class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int j = 1; j <= n2; j++) {
            dp[0][j] = dp[0][j - 1] + 1;
        }
        for (int i = 1; i <= n1; i++) {
            dp[i][0] = dp[i - 1][0] + 1;
        }
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                }
            }
        }
        return dp[n1][n2];
    }
}

时间：O(mn)，空间：O(mn)

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月30日上午12:27

时间空间复杂度都为O（mn）

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;
        for(int i = 1;i < m+1;i++){
            dp[i][0] = i;
        }
        for(int i = 1;i < n+1;i++){
            dp[0][i] = i;
        }
        for(int i = 1;i < m+1;i++){
            for(int j = 1;j < n+1;j++){
                if(word1.charAt(i-1) == word2.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[m][n];
    }
}

0 赞同 0 条回复

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

共以下 5 个回答

二维DP 和字符串DP的典型题

# 回答此问题取消回复

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

共以下 5 个回答

二维DP 和 字符串DP的典型题

# 回答此问题 取消回复

二维DP 和字符串DP的典型题

# 回答此问题取消回复