Pure DFS
go
func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
return dfs(word1, word2, m, n, dp)
}
func dfs(word1 string, word2 string, m, n int, dp [][]int) int {
if dp[m][n] > 0 {
return dp[m][n]
}
if m == 0 {
dp[0][n] = n
return n
}
if n == 0 {
dp[m][0] = m
return m
}
if word1[m-1] == word2[n-1] {
dp[m][n] = dfs(word1, word2, m-1, n-1, dp)
return dp[m][n]
}
dp[m][n] = 1 + min(
dfs(word1, word2, m, n-1, dp),
dfs(word1, word2, m-1, n, dp),
dfs(word1, word2, m-1, n-1, dp))
return dp[m][n]
}DP
go
func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
dp[i][0] = i
}
for i := range dp[0] {
dp[0][i] = i
}
for i := range word1 {
for j := range word2 {
if word1[i] == word2[j] {
dp[i+1][j+1] = dp[i][j]
} else {
dp[i+1][j+1] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i][j])
}
}
}
return dp[m][n]
}Space compression
go
func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
dp := [2][]int{}
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := range dp[0] {
dp[0][i] = i
}
for i := range word1 {
dp[(i+1)&1][0] = i + 1
for j := range word2 {
if word1[i] == word2[j] {
dp[(i+1)&1][j+1] = dp[i&1][j]
} else {
dp[(i+1)&1][j+1] = 1 + min(dp[(i+1)&1][j], dp[i&1][j+1], dp[i&1][j])
}
}
}
return dp[m&1][n]
}