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

共以下 1 个回答

• 塔底的仰望 永久会员 2023年9月16日 下午7:06

  dp[i][j] 的定义为第一个字符串长度为i，第二个字符串长度为j时，所需要的操作步数
  时间复杂度O(mn);空间复杂度O(mn)

  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 = 1; i <= n1; i++) {
              dp[i][0] = dp[i - 1][0] + 1;
          }
          for (int i = 1; i <= n2; i++) {
              dp[0][i] = dp[0][i - 1] + 1;
          }
  
          for (int i = 1; i <= n1; i++) {
              for (int j = 1; j <= n2; j++) {
                  //若word[i]==word2[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 条回复

  登录以回复