Skip to main content

72. Edit Distance

分析

  word1 -> word2
[i] == [j] dfs(i+1, j+1)
else {
min(
insert -> dfs(i, j+1),
delete -> dfs(i+1, j),
replace -> dfs(i+1, j+1)
) + 1 -> 这个是要算成操作的
}

边界情况
word1 word2
"" "abc" -> 3
"abc" "" -> 3
so max(len(word1), len(word2))

dp 和 dfs 感觉十分相似,不过 dfs 的思考负担更小一些,建议先写一遍dfs考虑清楚,再写dp 不过无论是用 dfs 还是 dp 这类问题都是子问题和原问题面临的解决方案是一样的 先分析清楚要处理有哪些情况,边缘case是关键

horse ros

题解

dfs

func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
var dfs func(i, j int) int
memo := map[[2]int]int{}

dfs = func(i, j int) int {
lenWord1, lenWord2 := m-i, n-j
var temp int
currentIndex := [2]int{i, j}
if lenWord1 == 0 || lenWord2 == 0 {
return max(lenWord1, lenWord2)
}
if memo[currentIndex] != 0 {
return memo[currentIndex]
}
if word1[i] == word2[j] {
temp = dfs(i+1, j+1)
} else {
insert, delete, replace := dfs(i, j+1), dfs(i+1, j), dfs(i+1, j+1)
temp = min(min(insert, delete), replace) + 1
}
memo[currentIndex] = temp
return temp
}

return dfs(0, 0)
}

func min(a, b int) int {
if a < b {
return a
}
return b
}


func max(a, b int) int {
if a > b {
return a
}
return b
}

dp

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


func min(a, b int) int {
if a < b {
return a
}
return b
}


func max(a, b int) int {
if a > b {
return a
}
return b
}