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

hi 普通 2023年12月21日下午11:50

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 把单词拆开，以字母为单位一个个来看
        int n = word1.size(), m = word2.size();
        word1 = ' '+ word1, word2 = ' ' + word2;

        //word1 中前i 个字母和word2 中前j 个字母相等所需的最小的操作数
        vector<vector<int>> dp(n + 1, vector<int>(m + 1)); 

        //二维dp 数组初始条件：i/j == 0 时的情况，单纯的删除或增加字符
        for(int i = 0; i <= n; i++) dp[i][0] = i;
        for(int j = 0; j <= m; j++) dp[0][j] = j;

        //计算二维数组中其它位置上的值（最小操作数）
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                if(word1[i] == word2[j]) dp[i][j] = dp[i - 1][j - 1];
                //与前面三个位置上的数有关
                else{
                    dp[i][j] =min(dp[i - 1][j - 1], min(dp[i - 1][j] , dp[i][j - 1])) + 1;
                }
            }

        return dp[n][m];   
    }
};

0 赞同 0 条回复

June 普通 2023年11月23日下午3:49

class Solution {
    public int minDistance(String word1, String word2) {
          int n = word1.length();
          int m = word2.length();
          if( m == 0 || n == 0)
            return m + n; // 有一个是长度为0
          int[][] dp = new int[n+1][m+1]; //表示word1前i个字符和word2前j个字符的最小编辑距离

          for(int i=0;i<n + 1;i++)
            dp[i][0] = i;
          for(int j=0;j<m + 1;j++)
            dp[0][j] = j;
          for(int i=1;i<n + 1;i++)
          {
              for(int j=1;j<m + 1;j++)
              {
                  if(word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min( dp[i][j-1],dp[i-1][j-1]-1));
                  else
                    dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min (dp[i][j-1],dp[i-1][j-1]));
              }
          }
          return dp[n][m];
    }
}

0 赞同 0 条回复

Marshan 普通 2023年9月9日下午11:46

还是有点模糊

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

        vector<vector<int>> dp(m+1,vector<int>(n+1,0));

        for(int i = 1;i <= m;++i){
            dp[i][0] = i;
        }
        for(int j = 1;j <= n;++j){
            dp[0][j] = j;
        }

        for(int i = 1;i <= m;++i){
            for(int j = 1;j <= n;++j){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = min(
                        min(dp[i-1][j]+1,
                        dp[i][j-1]+1),
                        dp[i-1][j-1]+1
                    );
                }
            }
        }
        return dp[m][n];
    }
};

0 赞同 0 条回复

Mby 普通 2023年8月22日下午1:17

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];
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月11日上午12:22

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

        // word1 的 [0, i - 1] 和 word2 的 [0, j - 1] 变成相同字符串，所需要的最少的操作数为dp[i][j]
        int[][] dp = new int[m + 1][n + 1];
        //初始化
        //word2为空字符串时
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        //word1为空字符串时
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; 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][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

        return dp[m][n];
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月9日下午11:26

8.9 周三
Day30：下面是代码

class Solution {
    public int minDistance(String word1, String word2) {
        //增 dp[i][j] = dp[i][j - 1] + 1;
        //删 dp[i][j] = dp[i - 1][j] + 1;
        //改 dp[i][j] = dp[i - 1][j - 1] + 1;
        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] = 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];
    }
}

0 赞同 0 条回复

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

共以下 6 个回答

# 回答此问题取消回复

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

共以下 6 个回答

# 回答此问题 取消回复

# 回答此问题取消回复