# **Leetcode筆記(Edit Distance)**
:::info
:information_source: 題目 : Edit Distance, 類型 : dynamic programming , 等級 : medium
日期 : 2023/12/08，2023/03/26，2024/09/29，2024/11/12
:::
### 嘗試
2023/03/26
記得在dp的時候，每次都要修正
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
dp = [[0] * (m + 1) for _ in range(n + 1)] # n * m
dp[0][0] = 0
def dfs(w1, w2, i1, i2):
# -1 means no character
if i1 == -1 and i2 == -1:
return 0
if i1 == -1: # w1 empty, add remaining w2
return i2 + 1 # cost要加1
if i2 == -1: # w2 empty, remove remaining w1
return i1 + 1
if dp[i1 + 1][i2 + 1]:
return dp[i1 + 1][i2 + 1]
cost = 0
if w1[i1] == w2[i2]:
cost += dfs(w1, w2, i1 - 1, i2 - 1)
else:
delete = dfs(w1, w2, i1 - 1, i2)
insert = dfs(w1, w2, i1, i2 - 1)
replace = dfs(w1, w2, i1 - 1, i2 - 1)
cost += (min(delete, insert, replace) + 1)
dp[i1 + 1][i2 + 1] = cost
return cost
return dfs(word1, word2, n - 1, m - 1)
```
2024/09/29
寫得不錯(https://labuladong.online/algo/dynamic-programming/edit-distance/#%E4%B8%80%E3%80%81%E6%80%9D%E8%B7%AF)
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
dp = [[-1] * m for _ in range(n)] # n * m
def dfs(s1, s2, i1, i2):
if i1 == -1:
return i2 + 1
if i2 == -1:
return i1 + 1
if dp[i1][i2] != -1:
return dp[i1][i2]
if s1[i1] == s2[i2]:
dp[i1][i2] = dfs(s1, s2, i1 - 1, i2 - 1)
else:
# delete s1, so s1 compare the previous
# bb ac -> b ac
delete = dfs(s1, s2, i1 - 1, i2) + 1
# insert on s1, so s2 == s1
# bb ac -> bb(c) a(c)
insert = dfs(s1, s2, i1, i2 - 1) + 1
# replace s1, so s2 == s1, both move to pre
# bb ac -> b(c) a(c)
replace = dfs(s1, s2, i1 - 1, i2 - 1) + 1
dp[i1][i2] = min(delete, insert, replace)
return dp[i1][i2]
return dfs(word1, word2, n - 1, m - 1)
```
2024/11/12
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
memo = [[-1] * m for _ in range(n)]
return self.traverse(word1, word2, 0, 0, memo)
def traverse(self, word1, word2, i, j, memo):
if i == len(word1) and j == len(word2):
return 0
if i == len(word1):
return len(word2) - j
if j == len(word2):
return len(word1) - i
if memo[i][j] != -1:
return memo[i][j]
if word1[i] != word2[j]:
replace = self.traverse(word1, word2, i + 1, j + 1, memo) + 1
delete = self.traverse(word1, word2, i + 1, j, memo) + 1
insert = self.traverse(word1, word2, i, j + 1, memo) + 1
memo[i][j] = min(replace, delete, insert)
else:
no_change = self.traverse(word1, word2, i + 1, j + 1, memo)
memo[i][j] = no_change
return memo[i][j]
```
普通dfs
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
self.min_cost = float("inf")
self.traverse(word1, word2, 0, 0, 0)
return self.min_cost
def traverse(self, word1, word2, i, j, cost):
if i == len(word1) and j == len(word2):
self.min_cost = min(self.min_cost, cost)
return
if i == len(word1):
self.min_cost = min(self.min_cost, cost + len(word2) - j)
return
if j == len(word2):
self.min_cost = min(self.min_cost, cost + len(word1) - i)
return
if word1[i] != word2[j]:
# replace
self.traverse(word1, word2, i + 1, j + 1, cost + 1)
# delete
self.traverse(word1, word2, i + 1, j, cost + 1)
# insert
self.traverse(word1, word2, i, j + 1, cost + 1)
else:
self.traverse(word1, word2, i + 1, j + 1, cost)
```
---
### **優化**
用cache(dp)去優化，因為我們會走到重複的步驟，cache裡面記錄當前的index，不會去改動到原始的word，所以index會是相同的，index 0 代表空字串
兩種情況
1. 當下兩個c相等，那直接比較下一個c，兩邊index都減1
2. 當下兩個c不相等，下去遍歷三種不一樣的情況，回傳候選最小的，加上當前的cost
會有cache的原因
**Time Complexity:** O(n * m)
The memoization approach ensures that, for every combination of `word1` and `word2`, the result is computed only once. The time complexity is determined by the number of unique subproblems, and since the memoization avoids redundant calculations, the time complexity is linear with respect to the product of the lengths of `word1` (M) and `word2` (N).
**Space Complexity:** O(n * m)
The space complexity is primarily due to the additional 2-dimensional array `memo` of size O(n * m). This array stores the results of subproblems, avoiding duplicate computations. Therefore, the space complexity is proportional to the product of the lengths of `word1` (M) and `word2` (N).
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0
def dfs(w1, w2, i1, i2):
if i1 == 0 and i2 == 0:
return 0
if w1 == w2:
return 0
if i1 == 0: # insert all c in word2
return i2
if i2 == 0: # delete all c in word1
return i1
# use the cache
if dp[i1][i2]:
return dp[i1][i2]
if w1[i1 - 1] == w2[i2 - 1]: # if c are same
cost = 0
cost = dfs(w1, w2, i1 - 1, i2 - 1) # go to the next level directly
else:
# check next level's operation
delete = dfs(w1, w2, i1 - 1, i2)
insert = dfs(w1, w2, i1, i2 - 1)
replace = dfs(w1, w2, i1 - 1, i2 - 1)
# +1 is for current operation
cost = 1
cost += min(delete, insert, replace)
# store result in dp
dp[i1][i2] = cost
return cost
return dfs(word1, word2, n, m)
```
---
**思路**
**講解連結**
Provided by.
Sign in with Wallet
Connect another wallet