WEI-CHENG CHEN

說明

計算最少的步數，將字串 a 變成字串 b

但只能進行這三種操作：

• 插入一個字元
• 刪除一個字元
• 替換一個字元

解法：DP

定義dp[i][j]為：將 word1 的前 i 個字元轉換成 word2 的前 j 個字元所需的最少操作數。

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

        // 第一次填充
        for (int i = 0; i < m+1; ++i) dp[i][0] = i;
        for (int j = 0; j < n+1; ++j) dp[0][j] = j;

        // 狀態轉移
        for (int i = 1; i < m+1; ++i){
            for (int j = 1; j < n+1; ++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][j-1],
                        dp[i-1][j-1]
                    })+1;
                }
            }
        }
        return dp[m][n];
    }
};