LeetCode 筆記 - 583. Delete Operation for Two Strings

Posted on

題目在此 583. Delete Operation for Two Strings

給定兩個字串，請找出最少將它們刪成一樣字串的次數

解題思維

同學，在這裡我們會用到 Longest Common Subsequence 的概念
如果沒解過可以先看這篇 LeetCode 筆記 - 1143. Longest Common Subsequence

我們在這裡先計算出 Longest Common Subsequence 的結果
因為 Longest Common Subsequence 是不會被刪掉的
而剩下的字元都會被刪掉

所以答案就變成 size1 + size2 - 2 * lcs

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        size1 = len(word1)
        size2 = len(word2)
        
        dp = [[0 for _ in range(size2)] for _ in range(size1)]
        
        for i in range(size1):
            for j in range(size2):
                if word1[i] == word2[j]:
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                    
        lcs = dp[-1][-1]
        
        return size1 + size2 - 2 * lcs

相關文章