題目： LeetCode - 72. Edit Distance

題目說明

給兩個 String word1、word2，求最少的操作數使得 word1 等於 word2。操作有以下三種：

  • 插入
  • 刪除
  • 取代

解題思路

動態規劃，核心想法為，目前這兩個字是否相等？若相等則表示不需要操作 dp[i][j] = dp[i - 1][j - 1]，若不相等則 dp[i][j] 為 dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1] 三者最小值加一。需要注意的是，邊界需要初始化。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int minDistance(string word1, string word2) {
        int l1 = word1.size(), l2 = word2.size();
        auto dp = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1));
        for(int i = 0; i <= l1; ++i)
            dp[i][0] = i;
        for(int j = 0; j <= l2; ++j)
            dp[0][j] = j;
        for(int i = 1; i <= l1; ++i)
            for(int j = 1; j <= l2; ++j)
                if(word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 1 + min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
        return dp[l1][l2];
    }
};