Delete Operation for Two Strings
Intuition
Solution
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
"""
Main part is to caculate longest common subquence
"""
if not word1 or not word2:
return len(word1) + len(word2)
length = [0] * len(word1)
for c in word2:
tmp = []
for j in range(len(word1)):
if word1[j] == c:
if j == 0:
tmp.append(1)
else:
tmp.append(max(length[j - 1] + 1, length[j]))
else:
if j == 0:
tmp.append(length[j])
else:
tmp.append(max(tmp[j - 1], length[j]))
length = tmp
l = max(length)
return len(word1) + len(word2) - 2 * l