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

共以下 5 个回答

• 宁 永久会员 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 条回复

  登录以回复