LeetCode - 72 Edit Distance

Medium

72. Edit Distance

題目

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)

Example 2

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)

Constraints

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

解題思路

經典字串 DP 題

• DP 定義：

  • dp[i][j]：word1 前 i 個字，變成 word2 前 j 個字，最少要幾步

• 初始化：

  • dp[i][0] = i
    • 把 word1 前 i 個字全部刪掉
  • dp[0][j] = j
    • 從空字串插入 j 個字變成 word2

• 狀態轉移：

  • 當 word1[i-1] == word2[j-1]

    • 不需要操作
      dp[i][j] = dp[i-1][j-1]

  • 否則從三個方向更新：

    • 從上面來（刪除）
      刪掉 word1[i-1]
dp[i][j] = dp[i-1][j] + 1

    • 從左上來（替換）
      把 word1[i-1] 換成 word2[j-1]
dp[i][j] = dp[i-1][j-1] + 1

    • 從左邊來（插入）
      插入 word2[j-1]
dp[i][j] = dp[i][j-1] + 1

  • 取最小值：

    • dp[i][j] = min({上, 左上, 左}) + 1

• 最後答案：

  • dp[n][m]

Solution Code

Time Complexity
O(n × m)

Space Complexity
O(n × m)

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();

        vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); // dp[i][j] = word1 前 i 個字，變成 word2 前 j 個字，最少要幾步

        /*
        三個方向更新 dp
        從上面來，代表 刪掉 word1 的第 i 個字
        從左上來，代表 把 word1的最後一個字換掉
        從左邊來，代表 插入 word2[j-1] 這個字
        */

        for(int i = 0; i <= n; ++i) dp[i][0] = i;
        for(int j = 0; j <= m; ++j) dp[0][j] = j;

        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min({dp[i-1][j], dp[i-1][j-1], dp[i][j-1]}) + 1;
            }
        }

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