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

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

要求：

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

shuaidi

更新于 3 年前 153 4

共以下 4 个回答

王位詮釋普通 2024年4月14日下午6:24

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        //dp[i][j]表示当word1长度为i，word2长度为j的时候
        //需要的最少的操作数
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;
        //初始化第一行
        for(int i=1;i<n+1;i++){
            dp[0][i] = dp[0][i-1]+1;
        }
        //初始化第一列
        for(int i=1;i<m+1;i++){
            dp[i][0] = dp[i-1][0]+1;
        }
        //把word1转换为word2所需要的最少步数
        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)){//i处的字符与j处的字符相等
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    int add = dp[i][j-1];//插入一个字符之前
                    int delete = dp[i-1][j];//删除一个字符之前
                    int replace = dp[i-1][j-1];//替换一个字符之前
                    dp[i][j] = Math.min(Math.min(add,delete),replace)+1;
                }
            }
        }
        return dp[m][n];
    }
}
思路：用二维数组记录长度为i的字符串word1转换为长度为j的字符串word2所需要的最少的操作数，如果word1的第i个字符和word2的第j个字符相同，则dp[i][j] =  dp[i-1][j-1]，否则就需要看是要怎么操作：添加一个字符、删除一个字符、替换一个字符。
时间复杂度：O(mn)
空间复杂度：O(mn)
优化成一维数组：
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[] dp = new int[n+1];
        //初始化
        for(int i=1;i<n+1;i++){
            dp[i] = dp[i-1]+1;
        }
        for(int i=1;i<m+1;i++){
            int temp = dp[0];
            dp[0] = dp[0]+1;
            for(int j=1;j<n+1;j++){
                int pre = temp;
                temp = dp[j];
                if(word1.charAt(i-1)==word2.charAt(j-1)){//word1第i个字符和word2第j个字符相等
                    dp[j] = pre;
                }else{
                    dp[j] = Math.min(Math.min(pre,dp[j-1]),dp[j])+1;
                }
            }
        }
        return dp[n];
    }
}
时间复杂度：O(mn)
空间复杂度：O(n)

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年4月9日下午6:52

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 i = 0; i <= n1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n2; j++){
            dp[0][j] = j;
        }

        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] =Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
                }
                else{
                    dp[i][j]=dp[i-1][j-1];
                }

            }
        }

        return dp[n1][n2];
    }
}

0 赞同 0 条回复

云无深雁影普通 2024年4月5日上午12:41
class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for(int i = 0; i < word1.length() + 1; i++)
dp[i][0] = i;
for(int j = 0; j < word2.length() + 1; j++)
dp[0][j] = j;
for(int i = 1; i < word1.length() + 1; i++){
for(int j = 1; j < word2.length() + 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[word1.length()][word2.length()];
```
}
```
}
//时空复杂度均为On2
0 赞同 0 条回复

登录以回复
紫芝普通 2024年4月4日下午11:41

思路：定义数组 dp[i][j] 表示 word1 的前 i 个字符串与 word2 的前 j 个字符串匹配的最小操作次数，则 dp[i][j] 可以有以下几种情况：
1. word1[i] word2[j]: dp[i][j] = dp[i-1][j-1]
2. word1[i] != word2[j]: dp[i][j] = min( dp[i-1][j-1](替换word1[i] word2[j]), dp[i-1][j] (删除 word1[i]), dp[i][j-1] (在 word1[i]后增加 word2[j]) ) + 1 (1 次操作次数)

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

0 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答

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

共以下 4 个回答

# 回答此问题 取消回复

# 回答此问题取消回复