Leetcode 72. Edit Distance

Edit Distance :

給定兩個字符串 word1 和 word2，返回將 word1 轉換為 word2 所需的最小操作數。

可以對單詞進行以下三個操作：

1.插入一個字符
2.刪除一個字符
3.替換一個字符

Python

動態規劃解 :

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        l1, l2 = len(word1), len(word2)
        dp1 = [i for i in range(l1 + 1)]
        dp2 = [0] * (l1 + 1)
        for i in range(1, l2 + 1):
            dp2[0] = i
            for j in range(1, l1 + 1):
                if word2[i - 1] == word1[j - 1]:
                    dp2[j] = dp1[j - 1]
                else:
                    dp2[j] = min(dp1[j - 1], dp2[j - 1], dp1[j]) + 1
            dp1 = dp2[:]
        return dp1[-1]

C++

可以使用動態規劃來解決這個問題，定義一個二維數組 dp，其中 dp[i][j] 表示將 word1 中前 i 個字符轉換成 word2 中前 j 個字符所使用的最少操作數。

初始化 dp 數組如下：

dp[i][0] = i; // word2 為空，從 word1 刪除 i 個字符
dp[0][j] = j; // word1 為空，從 word2 插入 j 個字符

接下來，考慮 dp[i][j] 如何通過 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 轉移得到。

如果 word1[i] == word2[j]，則 dp[i][j] = dp[i-1][j-1]，即不需要進行操作。

如果 word1[i] != word2[j]，則 dp[i][j] 可以通過 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 中的最小值加 1 得到，即：

dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1;

最後返回 dp[m][n] 即可，其中 m 和 n 分別為 word1 和 word2 的長度。

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));
    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-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
                    }
            }
        }
        return dp[m][n];
        }
};