###### tags: `Leetcode` `hard` `dynamic programming` `python` `Top 100 Liked Questions`

# 72. Edit Distance

## [題目連結:]https://leetcode.com/problems/edit-distance/

## 題目:
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

* Insert a character
* Delete a character
* Replace a character

**Example 1:**

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

**Example 2:**

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

## 解題想法:
* 題目要求將word1改成word2，可進行三種操作:
* 添加一個字
* 刪除一個字
* 取代一個字
* example: word1="horse" word2="ros"
* dp[ [0 for _ in range(len(word2)+1)] for _ in range(len(word1)+1)]
* 初始:
* 第一列: 0,1,2,3對應的意思為:
* word1:'沒有字',要成為word2:'沒有字'->操作次數0
* word1:'沒有字',要成為word2:'r' ->操作次數1 (by Insert a character)
* 第一行: 0,1,2,3,4,5對應的意思為:
* word1:'h', 要成為word2:'沒有字'->操作次數1 (by Delete a character)
* word1:'ho', 要成為word2:'沒有字'->操作次數2 (by Delete a character)
* **dp[i][j]: word1前面i個字符更改成word2前面j個字符的操作次數**
* 轉移方程: dp[i][j]=
* **dp[i-1][j-1]，**
* 若當前w1[i-1]==w2[j-1]，
* 直接繼承前一組，表示不用進行任何操作
* **min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1**
* case1: dp[i-1][j-1]+1
* 左上一組字串操作數，讓當前w1[i]轉換成w2[j] (Replace a character)
* case2: dp[i-1][j]+1:
* 上面一組字串操作數，刪除當前w1[i] (Delete a character)
* case3: dp[i][j-1]+1:
* 左邊一組字串操作數，添加w2[j] (Insert a character)

| w1 \ w2 | - | r | o | s |
|:-------:|:---:|:---: |:---: |:---: |
| - | 0 | 1 | 2 | 3 |
| h | 1 | **1** | **2** | **3** |
| o | 2 | 2 | 1 | 2 |
| r | 3 | 2 | 2 | 2 |
| s | 4 | 3 | 3 | 2 |
| e | 5 | 4 | 4 | **3** |

* dp[1][1]=1
* w1="h"，w2="r"
* 由左上角w1=None,w2=None，Insert "R" 讓w1=w2
* dp[1][2]=2
* w1="h" w2="ro"
* 可由左上角or左邊 inert"R" 讓w1=w2
* 最終dp[-1][-1]=3
* w1="horse" w2="ros"
* 表示操作3次運算即可

## Python:

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m=len(word1)
        n=len(word2)
        dp=[ [0 for _ in range(n+1)] for _ in range(m+1)]
        #init:
        for i in range(1,m+1):
            dp[i][0]=i
        for j in range(1,n+1):
            dp[0][j]=j
        #dp
        for i in range(1,m+1):
            for j in range(1,n+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-1][j],dp[i][j-1])+1
        return dp[-1][-1]
    
if __name__ == '__main__':
    result=Solution()
    ans=result.minDistance(word1 = "horse", word2 = "ros")
    print(ans)