Solution to LeetCode 583 Delete Operation for Two Strings and LeetCode 72 Edit Distance
LeetCode 583
Delete Operation for Two Strings (Medium) [link]
Define dp[i][j] as the minimum number of deletion of word1[0:i-1] and word2[0:j-1] to make them the same.
Case1: word1[i-1]==word2[j-1]. dp[i][j] = dp[i - 1][j - 1].
Case2: word1[i-1]!=word2[j-1]. dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i - 1][j-1]+2).
Initialize dp[i][0] and dp[0][j]. dp[i][0]=i and dp[0][j]=j.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(word1)+1):
dp[i][0] = i
for j in range(len(word2)+1):
dp[0][j] = j
for i in range(1, len(word1)+1):
for j in range(1, len(word2)+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i - 1][j-1]+2)
return dp[-1][-1]
LeetCode 72
Edit Distance (Hard) [link]
We can Insert, delete, or replace a character.
Define dp[i][j] as the minimum number of editions of word1[0:i-1] and word2[0:j-1] to make them the same.
Case 1: word1[i-1]==word2[j-1]. We do nothing. dp[i][j] = dp[i - 1][j - 1].
Case 2: word1[i-1]!=word2[j-1]. We do insert, delete, or replace. dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1.
The difference between LC72 and LC583 is that in LC72 we allow to replace a character so we don’t need to delete one character from both words.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
for i in range(len(word1)+1):
dp[i][0] = i
for j in range(len(word2)+1):
dp[0][j] = j
for i in range(1, len(word1)+1):
for j in range(1, len(word2)+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i - 1][j-1]+1)
return dp[-1][-1]
