九号球普通 2023年12月9日上午11:49

“`java
class Solution {
public int minDistance(String word1, String word2) {
//word1前i位转换word2前j位所有步数为dp[i][j]
//word[i] = word[j]，则dp[i][j] = dp[i-1][j-1];
//word[i] != word[j]，则有三种操作，插入，删除，替换
//dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j],dp[i][j+1]) + 1;
int l1 = word1.length();
int l2 = word2.length();
if (l1 == 0){
return l2;
}
if (l2 == 0){
return l1;
}
int[][] dp = new int[l1+1][l2+1];
//word1长度为0时
for (int j = 0; j <= l2; j++) { dp[0][j] = j; } //word2长度为0时 for (int i = 0; i <= l1; i++) { dp[i][0] = 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(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1; } } } return dp[l1][l2]; } }

0 赞同 0 条回复

yxy 普通 2023年7月25日下午4:14

好难

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) return n + m;

        // DP 数组
        vector<vector<int>> D(n + 1, vector<int>(m + 1));

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1]) left_down += 1;
                D[i][j] = min(left, min(down, left_down));

            }
        }
        return D[n][m];
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月24日下午9:17

MY

// 这是中文
class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.length(), m = b.length();
        a = ' ' + a, b = ' ' + b;

        vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MAX));

        for (int i = 0; i <= n; i++) f[i][0] = i;
        for (int j = 0; j <= m; j++) f[0][j] = j;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
                else {
                    f[i][j] = min(f[i - 1][j - 1], min(f[i][j - 1], f[i - 1][j])) + 1;
                }
            }
        }
        return f[n][m];
    }
};

0 赞同 0 条回复

张开怀普通 2023年7月24日下午8:13

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) return n + m;

        // DP 数组
        vector<vector<int>> D(n + 1, vector<int>(m + 1));

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1]) left_down += 1;
                D[i][j] = min(left, min(down, left_down));

            }
        }
        return D[n][m];
    }
};

时间复杂度：O(mn)
空间复杂度：O(mn)

0 赞同 0 条回复

花老爷普通 2023年7月23日下午5:10

动态规划，官解，好难
时间：O(mn)
空间：O(mn)

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) {
            return n + m;
        }

        // DP 数组
        int[][] D = new int[n + 1][m + 1];

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return D[n][m];
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年7月23日下午3:55

C++实现

“`C++
class Solution {
public:
int minDistance(string word1, string word2) {
vector> dp(word1.size() + 1, vector(word2.size() + 1, 0));

    for (int i = 0; i < dp.size(); i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j < dp[0].size(); j++) {
        dp[0][j] = j;
    }
    //dp数组可以优化为一维
    for (int i = 1; i < dp.size(); i++) {
        for (int j = 1; j < dp[i].size(); j++) {
            dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            }
        }
    }
    return dp[word1.size()][word2.size()];
}

};

“`

0 赞同 0 条回复

Vow the vow。普通 2023年7月23日下午3:07

做一次看一次答案系列

public int minDistance(String word1, String word2) {
        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();
        int len1 = s1.length,len2 = s2.length;
        int[][] f= new int[len1+1][len2+1];
        for(int i = 1; i <= len1; i++) f[i][0] = i;
        for(int j = 1; j <= len2; j++) f[0][j] = j;
        for(int i = 0; i < len1; i++){
            for(int j = 0; j < len2; j++){
                if(s1[i] == s2[j]){
                    f[i+1][j+1] = f[i][j];
                }else{
                    f[i+1][j+1] = Math.min(f[i][j+1],Math.min(f[i+1][j],f[i][j]))+1;
                }
            }
        }
        return f[len1][len2];

    }

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月23日上午5:53

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(n + 1):
            dp[0][i] = i

        for i in range(m + 1):
            dp[i][0] = i

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if (word1[i - 1] != word2[j - 1]):
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                else:
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[m][n]

动态规划

0 赞同 0 条回复

Yodl. 普通 2023年7月22日下午6:15

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        for (int i = 0; i < dp.size(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < dp[0].size(); j++) {
            dp[0][j] = j;
        }
        //dp数组可以优化为一维
        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[i].size(); j++) {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

0 赞同 0 条回复

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

共以下 9 个回答

MY

# 回答此问题取消回复

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

共以下 9 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复