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
andword2
consist of only lowercase English letters.
這題和 72. 很像,但是沒有 Replace,只有 Delete 和 Insert
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][0] = i
}
for j:=0; j<=n; j++ {
dp[0][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
}