583两个字符串的删除操作
代码如下
func minDistance(word1 string, word2 string) int { dp[i][j]的含义是下标为i-1和下标为j-1的两个数组的最小操作数
dp := make([][]int,len(word1)+1)
for i,_ := range dp {
dp[i] = make([]int,len(word2)+1)
}
for i := 0 ; i <= len(word1) ; i++ { dp[i][0]的意思为如果一个数组长度为i，另一个为空，那么需要的操作数是i
dp[i][0] = i
}
for j := 0 ; j <= len(word2) ; j++ { 同理
dp[0][j] = j
}
for i := 1 ; i <= len(word1) ; i++ {
for j := 1 ; j <= len(word2) ; j++ {
if word1[i-1] == word2[j-1] { 如果这两个数相同，则不需要任何操作让他们相同
dp[i][j] = dp[i-1][j-1]
}else { 如果这两个数不同，则可能需要三种操作，一是删除数组1的元素，二是删除数组2的元素，3是删除数组1和2的元素 。因为这个数都是从前面推出来的，所以遍历到i-1和j-1时说明这两个数组经过dp[i-1][j-1]个操作数已经相同，那么就删除这两个元素即可，所以操作数加2 同理，可能两个数组经过dp[i][j-1]个操作数相同，那么就需要删除j-1这个数，所以操作数加1
dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+2))
}
}
}
return dp[len(word1)][len(word2)]
}
func min(a,b int) int {
if a < b {
return a
}else {
return b
}
}
72 编辑距离
代码如下
func minDistance(word1 string, word2 string) int {
dp := make([][]int,len(word1)+1)
for i,_ := range dp {
dp[i] = make([]int,len(word2)+1)
}
for i := 0 ; i <= len(word1) ; i++ {
dp[i][0] = i
}
for j := 0 ; j <= len(word2) ; j++ {
dp[0][j] = j
}
for i := 1 ; i <= len(word1) ; i++ {
for j := 1 ; j <= len(word2) ; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
}else { 和上面一题基本差不多，就是当两个数不相同时，可以有三个操作，删除，增加或者替换，删除和添加互为逆运算所以操作数相同，而替换，则说明在没有比较这两个数之前进行dp[i-1][j-1]个操作可以使得两个数组相同，那么就只要进行一次替换操作即可。而删除操作则是，删除一个数组里的元素即可，为什么不需要同时删除两个元素，因为如果需要删除两个元素，那么其实可以进行替换操作
dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1))
}
}
}
return dp[len(word1)][len(word2)]
}
func min(a,b int) int {
if a < b {
return a
}else {
return b
}
}
