问题描述
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.
问题分析
2个字符串在尽量少的删除某些字符后相同， 说明剩余的字符为这2个字符的最大公共子序列（注意不是最大公共子串） 那么我们仅需求出目标字符串的最大公共子序列长度，用各自的长度减去该长度，即为最少需要的操作次数
示例代码
func minDistance(word1 string, word2 string) int {
// 求最大公共子序列 https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97
// dp[i][j]表示word1[:i], word2[:j]之间的最大公共子序列
// 则有 dp[i][j] = max(dp[i-1][j-1]+1?, dp[i-1][j], dp[i][j-1])
len1, len2 := len(word1), len(word2)
dp := [][]int{}
for i := 0; i <= len1; i++ {
dp = append(dp, make([]int, len2+1))
}
// base case
dp[1][1] = same(word1[0], word2[0])
for i := 1; i <= len1; i++ {
for j := 1; j <= len2; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return len1 - dp[len1][len2] + len2 - dp[len1][len2]
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func same(a byte, b byte) int {
if a == b {
return 1
}
return 0
}