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

共以下 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 条回复

  登录以回复