题目描述
edit-distance
分析
Q1 我如何知道从一个单词 变成另外一个单词 需要做那个操作合适？插入|删除|替换 无限大问题 无法入手
每次操作一次字符 算一次编辑距离
操作次数o(n) 这是不是最优解
视频地址：https://www.youtube.com/watch?v=Q4i_rqON2-E
image.png
https://leetcode.com/problems/edit-distance/discuss/25849/Java-DP-solution-O(nm)
https://leetcode.com/problems/edit-distance/discuss/146320/cpp-dp-beats-99.9-8ms
https://leetcode.com/problems/edit-distance/discuss/25846/20ms-Detailed-Explained-C++-Solutions-(O(n)-Space)
代码
go 递归
func minDistance(word1 string, word2 string) int {
n := len(word1)
m := len(word2)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, m+1)
//数组的(n-1,m-1)对应dp存储的(n,m)
}
return minDistanceDP(dp, word1, word2, n, m)
}
func minDistanceDP(dp [][]int, word1 string, word2 string, n int, m int) int {
//一个空字符串变成字符串方式 只有一种 添加m个字符串
if n == 0 {
return m
}
if m == 0 {
return n
}
//已经计算过的
if dp[n][m] > 0 {
return dp[n][m]
}
if word1[n-1] == word2[m-1] {
//fun(abc)->fun(akc) ->fun(ab)->fun(ak)
dp[n][m] = minDistanceDP(dp, word1, word2, n-1, m-1)
} else {
//一个字符串做A做一次变化操作变成字符串B 特点 字符A和字符串B 只有一个字符差异 其余都相同 寻找相部分
//替换操作：fun(a)->func(b) 上个状态是空字符串fun("")->fun("")+替换操作 fun(i-1)->fun(j-1)的编辑距离
//添加 fun(a)-fun(ab) 上个状态是fun(a)->fan(a) +添加操作 fun(i)->fun(j-1)的编辑距离
//删除 fun(ab)-fun(a) 上个状态是fun(a)->fan(a) +删除操作操作 fun(i-1)->fun(j)的编辑距离
replace := minDistanceDP(dp, word1, word2, n-1, m-1) + 1
add := minDistanceDP(dp, word1, word2, n, m-1) + 1
del := minDistanceDP(dp, word1, word2, n-1, m) + 1
dp[n][m] = min(replace, min(add, del))
}
fmt.Println(word1, word2, n, m, dp[n][m])
return dp[n][m]
}
go动态规划
func minDistance1(word1 string, word2 string) int {
//We define the state dp[i][j] to be the minimum number of operations to convert word1[0..i - 1] to word2[0..j - 1]
n := len(word1)
m := len(word2)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, m+1)
//数组的(n-1,m-1)对应dp存储的(n,m)
}
// 默认值
for i := 0; i <= n; i++ {
dp[i][0] = i
}
for j := 0; j <= m; j++ {
dp[0][j] = j
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; 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-1], min(dp[i-1][j], dp[i][j-1]))
}
}
}
return dp[n][m]
}
总结
类似问题：
image.png
61.One Edit Distance
Given two strings s and t, determine if they are both one edit distance apart.
Note:
There are 3 possiblities to satisify one edit distance apart:
Insert a character into s to get t
Delete a character from s to get t
Replace a character of s to get t
Example 1:
Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.
Example 2:
Input: s = "cab", t = "ad"
Output: false
Explanation: We cannot get t from s by only one step.
Example 3:
Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.
