---
# System prepended metadata

title: '**Leetcode筆記(Edit Distance)**'
tags: [medium, microsoft, dynamic programming, leetcode]

---

# **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的原因
![image](https://hackmd.io/_uploads/B1ZZsUgk0.png =70%x)



**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. 
