72. Edit Distance

題目網址：https://leetcode.cn/problems/edit-distance/

題意：給兩 string word1 和 word2, 返回將 word1 轉換成 word2 的最少操作數。

可對單字進行以下操作：

• 插入一個 char
• 刪除一個 char
• 替換一個 char

!https://i.imgur.com/Lw9oEAc.png

Solution：

想法：利用 DP

1. 定義狀態：

• dp[i][j]：word1[1:i] 轉換成 word2[1:j] 的最少操作數

2. 得到轉移方程：

• 若 word1[i] == word2[j], 則問題變成 word1[1:(i-1)] 轉換成 word2[1:(j-1)] 的最少操作數
  ➔ dp[i][j] = dp[i - 1][j - 1]

• 否則, 有三種情況：

  • word1[1:i] 插入 word2[j], 則問題變成 word1[1:i] 轉換成 word2[1:(j-1)] 的最少操作數 + 1（+1 是因為插入操作）
    ➔ dp[i][j] = dp[i][j - 1] + 1

  • word1[1:i] 刪除 word1[i], 則問題變成 word1[1:(i-1)] 轉換成 word2[1:j] 的最少操作數 + 1（+1 是因為刪除操作）
    ➔ dp[i][j] = dp[i - 1][j] + 1

  • word1[1:i] 替換 word1[i] 成 word2[j], 則問題變成 word1[1:(i-1)] 轉換成 word2[1:(j-1)] 的最少操作數 + 1（+1 是因為替換操作）
    ➔ dp[i][j] = dp[i - 1][j - 1] + 1

  ➔ dp[i][j] 為以上三種情況取最小的

3. 初始化：

• dp[i][0]：當 word2 = "" 時, word1[1:i] 必須刪除所有的 char 才會匹配 word2, 所以 word1[1:i] 必須進行 i 次刪除操作（因為有 i 個 char）
  ➔ dp[i][0] = i

• dp[0][j]：當 word1 = "" 時, word1 必須插入 word2[1:j] 中所有的 char 才會匹配 word2[1:j], 所以 word1 必須進行 j 次插入操作（因為有 ｊ 個 char）
  ➔ dp[0][j] = j

class Solution {
public:
    int minDistance(string word1, string word2) {
        const int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        word1 = '#' + word1;
        word2 = '#' + word2;

        for (int i = 0; i <= m; ++i) {
            dp[i][0] = i;
        }

        for (int j = 0; j <= n; ++j) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i] == word2[j]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else { // 三種情形中取最小的
                    dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1;
                }
            }
        }

        return dp[m][n];
    }
};

• time：$O(m \cdot n)$ ➔ for loop
• space：$O(m \cdot n)$ ➔ dp