題目： LeetCode - 583. Delete Operation for Two Strings

題目說明

給兩個 String，求刪除最少的字元數使兩者相等。

解題思路

可將問題想成，找出兩者的 LCS 在將兩者的長度個別減去 LCS 的值即為答案。
找 LCS 的作法可參考本篇文章：LeetCode - 1143 解題紀錄。

參考解法

1
2
3
4
5
6
7
8
9
10
11
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, 0));
        for(int i = 1; i <= l1; ++i)
            for(int j = 1; j <= l2; ++j)
                dp[i][j] = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        return l1 + l2 - dp[l1][l2] * 2;
    }
};