LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 动态规划，dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符所需要的最少次数

$$$a  // a代表word[i - 1]
@@@b  // b代表word[j - 1]

方式1：a 替换为 b
ab 相同，则只需要 $$$ 转换为 @@@ => dp[i][j] = dp[i - 1][j - 1]
ab 不同，则额外需要将 a 替换为 b => dp[i][j] = dp[i - 1][j - 1] + 1
方式2：word1 删除 a => dp[i][j] = dp[i - 1][j] + 1
方式3：word2 删除 b（等价于 word1 添加 b）=> dp[i][j] = dp[i][j - 1] + 1

• 解法如下

class Solution {
 public:
  int minDistance(string word1, string word2) {
    int m = size(word1);
    int n = size(word2);
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
      dp[i][0] = i;
    }
    for (int i = 1; i <= n; ++i) {
      dp[0][i] = i;
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int r = (word1[i - 1] == word2[j - 1]) ? dp[i - 1][j - 1]
                                               : dp[i - 1][j - 1] + 1;
        int d = dp[i - 1][j] + 1;
        int u = dp[i][j - 1] + 1;
        dp[i][j] = min({d, r, u});
      }
    }
    return dp[m][n];
  }
};