this problem is like longest common subsequence.
each time we can do insert, delete, replace operation.
operation and pointers
let's assume there's two pointer i, j, pointing to text1 and text2 respectively.
we only do operation in text1
insert: insert the same char of text2 to text1, then we'll keep comparing i with j + 1 (next char of text2)
delete: delete the cur char of text1, then comparing i + 1 with j
replace: change the cur char to char of text2, then move to next comparison (i + 1, j + 1)
DP buttom up technique
we first should update from buttom-right to top-left
remember that the boundary cells are not all zero, we can imagine that the operations counts needed to make empty strings into text2.
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for row in range(m):
dp[row][-1] = m - row
for col in range(n):
dp[-1][col] = n - col
for row in list(range(m))[::-1]:
for col in list(range(n))[::-1]:
if word1[row] == word2[col]:
dp[row][col] = dp[row + 1][col + 1]
else:
dp[row][col] = min(dp[row + 1][col], dp[row][col + 1], dp[row + 1][col + 1]) + 1
return dp[0][0]
this problem is like longest common subsequence. each time we can do
insert,delete,replaceoperation.operation and pointers
let's assume there's two pointer i, j, pointing to text1 and text2 respectively. we only do operation in text1 insert: insert the same char of text2 to text1, then we'll keep comparing i with j + 1 (next char of text2) delete: delete the cur char of text1, then comparing i + 1 with j replace: change the cur char to char of text2, then move to next comparison (i + 1, j + 1)
DP buttom up technique
we first should update from buttom-right to top-left remember that the boundary cells are not all zero, we can imagine that the operations counts needed to make empty strings into text2.