共以下 9 个回答

• 九号球 普通 2023年12月9日 上午11:49

  “`java
  class Solution {
  public int minDistance(String word1, String word2) {
  //word1前i位转换word2前j位所有步数为dp[i][j]
  //word[i] = word[j]，则dp[i][j] = dp[i-1][j-1];
  //word[i] != word[j]，则有三种操作，插入，删除，替换
  //dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j],dp[i][j+1]) + 1;
  int l1 = word1.length();
  int l2 = word2.length();
  if (l1 == 0){
  return l2;
  }
  if (l2 == 0){
  return l1;
  }
  int[][] dp = new int[l1+1][l2+1];
  //word1长度为0时
  for (int j = 0; j <= l2; j++) { dp[0][j] = j; } //word2长度为0时 for (int i = 0; i <= l1; i++) { dp[i][0] = 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(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1; } } } return dp[l1][l2]; } }

  0 赞同 0 条回复

  登录以回复
• yxy 普通 2023年7月25日 下午4:14

  好难

  class Solution {
  public:
      int minDistance(string word1, string word2) {
          int n = word1.length();
          int m = word2.length();
  
          // 有一个字符串为空串
          if (n * m == 0) return n + m;
  
          // DP 数组
          vector<vector<int>> D(n + 1, vector<int>(m + 1));
  
          // 边界状态初始化
          for (int i = 0; i < n + 1; i++) {
              D[i][0] = i;
          }
          for (int j = 0; j < m + 1; j++) {
              D[0][j] = j;
          }
  
          // 计算所有 DP 值
          for (int i = 1; i < n + 1; i++) {
              for (int j = 1; j < m + 1; j++) {
                  int left = D[i - 1][j] + 1;
                  int down = D[i][j - 1] + 1;
                  int left_down = D[i - 1][j - 1];
                  if (word1[i - 1] != word2[j - 1]) left_down += 1;
                  D[i][j] = min(left, min(down, left_down));
  
              }
          }
          return D[n][m];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• Dsjh 普通 2023年7月24日 下午9:17

  MY

  // 这是中文
  class Solution {
  public:
      int minDistance(string a, string b) {
          int n = a.length(), m = b.length();
          a = ' ' + a, b = ' ' + b;
  
          vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MAX));
  
          for (int i = 0; i <= n; i++) f[i][0] = i;
          for (int j = 0; j <= m; j++) f[0][j] = j;
  
          for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= m; j++) {
                  if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
                  else {
                      f[i][j] = min(f[i - 1][j - 1], min(f[i][j - 1], f[i - 1][j])) + 1;
                  }
              }
          }
          return f[n][m];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 张开怀 普通 2023年7月24日 下午8:13

  class Solution {
  public:
      int minDistance(string word1, string word2) {
          int n = word1.length();
          int m = word2.length();
  
          // 有一个字符串为空串
          if (n * m == 0) return n + m;
  
          // DP 数组
          vector<vector<int>> D(n + 1, vector<int>(m + 1));
  
          // 边界状态初始化
          for (int i = 0; i < n + 1; i++) {
              D[i][0] = i;
          }
          for (int j = 0; j < m + 1; j++) {
              D[0][j] = j;
          }
  
          // 计算所有 DP 值
          for (int i = 1; i < n + 1; i++) {
              for (int j = 1; j < m + 1; j++) {
                  int left = D[i - 1][j] + 1;
                  int down = D[i][j - 1] + 1;
                  int left_down = D[i - 1][j - 1];
                  if (word1[i - 1] != word2[j - 1]) left_down += 1;
                  D[i][j] = min(left, min(down, left_down));
  
              }
          }
          return D[n][m];
      }
  };
  

  时间复杂度：O(mn)
  空间复杂度：O(mn)

  0 赞同 0 条回复

  登录以回复
• 花老爷 普通 2023年7月23日 下午5:10

  动态规划，官解，好难
  时间：O(mn)
  空间：O(mn)

  class Solution {
      public int minDistance(String word1, String word2) {
          int n = word1.length();
          int m = word2.length();
  
          // 有一个字符串为空串
          if (n * m == 0) {
              return n + m;
          }
  
          // DP 数组
          int[][] D = new int[n + 1][m + 1];
  
          // 边界状态初始化
          for (int i = 0; i < n + 1; i++) {
              D[i][0] = i;
          }
          for (int j = 0; j < m + 1; j++) {
              D[0][j] = j;
          }
  
          // 计算所有 DP 值
          for (int i = 1; i < n + 1; i++) {
              for (int j = 1; j < m + 1; j++) {
                  int left = D[i - 1][j] + 1;
                  int down = D[i][j - 1] + 1;
                  int left_down = D[i - 1][j - 1];
                  if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                      left_down += 1;
                  }
                  D[i][j] = Math.min(left, Math.min(down, left_down));
              }
          }
          return D[n][m];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 怀瑾 永久会员 2023年7月23日 下午3:55

  C++实现

  “`C++
  class Solution {
  public:
  int minDistance(string word1, string word2) {
  vector> dp(word1.size() + 1, vector(word2.size() + 1, 0));

      for (int i = 0; i < dp.size(); i++) {
          dp[i][0] = i;
      }
      for (int j = 0; j < dp[0].size(); j++) {
          dp[0][j] = j;
      }
      //dp数组可以优化为一维
      for (int i = 1; i < dp.size(); i++) {
          for (int j = 1; j < dp[i].size(); j++) {
              dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
              if (word1[i - 1] == word2[j - 1]) {
                  dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
              }
          }
      }
      return dp[word1.size()][word2.size()];
  }
  

  };

  “`

  0 赞同 0 条回复

  登录以回复
• Vow the vow。 普通 2023年7月23日 下午3:07

  做一次看一次答案系列

  public int minDistance(String word1, String word2) {
          char[] s1 = word1.toCharArray();
          char[] s2 = word2.toCharArray();
          int len1 = s1.length,len2 = s2.length;
          int[][] f= new int[len1+1][len2+1];
          for(int i = 1; i <= len1; i++) f[i][0] = i;
          for(int j = 1; j <= len2; j++) f[0][j] = j;
          for(int i = 0; i < len1; i++){
              for(int j = 0; j < len2; j++){
                  if(s1[i] == s2[j]){
                      f[i+1][j+1] = f[i][j];
                  }else{
                      f[i+1][j+1] = Math.min(f[i][j+1],Math.min(f[i+1][j],f[i][j]))+1;
                  }
              }
          }
          return f[len1][len2];
  
      }
  

  0 赞同 0 条回复

  登录以回复
• 哈哈哈哈开开心心 普通 2023年7月23日 上午5:53

  class Solution:
      def minDistance(self, word1: str, word2: str) -> int:
          m, n = len(word1), len(word2)
          dp = [[0] * (n + 1) for _ in range(m + 1)]
  
          for i in range(n + 1):
              dp[0][i] = i
  
          for i in range(m + 1):
              dp[i][0] = i
  
          for i in range(1, m + 1):
              for j in range(1, n + 1):
                  if (word1[i - 1] != word2[j - 1]):
                      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                  else:
                      dp[i][j] = dp[i - 1][j - 1]
  
          return dp[m][n]
  

  动态规划

  0 赞同 0 条回复

  登录以回复
• Yodl. 普通 2023年7月22日 下午6:15

  class Solution {
  public:
      int minDistance(string word1, string word2) {
          vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
  
          for (int i = 0; i < dp.size(); i++) {
              dp[i][0] = i;
          }
          for (int j = 0; j < dp[0].size(); j++) {
              dp[0][j] = j;
          }
          //dp数组可以优化为一维
          for (int i = 1; i < dp.size(); i++) {
              for (int j = 1; j < dp[i].size(); j++) {
                  dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                  if (word1[i - 1] == word2[j - 1]) {
                      dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                  }
              }
          }
          return dp[word1.size()][word2.size()];
      }
  };
  

  0 赞同 0 条回复

  登录以回复