[LeetCode][Hard] 72. Edit Distance

Leetcode 網址: https://leetcode.com/problems/edit-distance/

題目說明:

給定二個字串 word1 以及 word2，請找出最少需要幾個操作才能將將 word1 轉換成 word2。

操作的定義有三種:   

1. 新增字元

2. 刪除字元

3. 取代字元

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

解題說明:

遇到這種題目一開始沒有想法的話就先將 input 變小，

以範例 1 的而言，我們慢慢將 input 由小至大就可以推論出下表: 

最後根據上表及推導中可以發現這題是個 Dynamic Programming 題型，

將推導的結果寫成演算法即可解決此題。

程式碼

class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[word1.length() + 1][word2.length() + 1];
        memset(&dp[0][0], 0, (word1.length() + 1) * (word2.length() + 1) * sizeof(int));
        
        for (int i = 1; i <= word1.length(); i++) dp[i][0] = i;
        for (int i = 1; i <= word2.length(); i++) dp[0][i] = i;
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
        return dp[word1.length()][word2.length()];
    }
};

結果

Runtime: 4 ms, faster than 97.72% of C++ online submissions for Edit Distance.

Memory Usage: 7.2 MB, less than 92.12% of C++ online submissions for Edit Distance.