LeetCode 筆記 - 583. Delete Operation for Two Strings

題目在此 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

也許你也會想看看