# 583. Delete Operation for Two Strings

Medium
Given two strings `word1` and `word2`, return the minimum number of steps required to make `word1` and `word2` the same.
In one step, you can delete exactly one character in either string.
Example 1:
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Example 2:
Input: word1 = "leetcode", word2 = "etco"
Output: 4
Constraints:
• `1 <= word1.length, word2.length <= 500`
• `word1` and `word2` consist of only lowercase English letters.

### 解題

func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, 0)
for i:=0; i<=m + 1; i++ {
dp = append(dp, make([]int, n + 1))
}
for i:=0; i<=m; i++ {
dp[i] = i
}
for j:=0; j<=n; j++ {
dp[j] = j
}
for i:=1; i<=m; i++ {
for j:=1; j<=n; j++ {
if word1[i - 1] == word2[j - 1] {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[m][n]
}
func min(a, b int) int {
if a < b { return a }
return b
}