Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 72. Edit Distance

---

參考資訊：
https://algo.monster/liteproblems/72
https://www.youtube.com/watch?v=reICpCoC97Y
https://www.cnblogs.com/grandyang/p/4344107.html

題目：


提示：


解答：

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

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

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

        for (int i = 1; i <= w1_size; ++i) {
            for (int j = 1; j <= w2_size; ++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[w1_size][w2_size];
    }
};