题目描述
给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
样例
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
算法1
(动态规划) $O(n^2)$
定义状态f[i][j]为s1串的前i个字符和s2串的前j个字符之间的距离。由编辑规则可知存在四种状态转移规则:
1. 当s[i] == s[j]时,f[i][j] = f[i-1][j-1]
2. 当s[i] != s[j]时,f[i][j] 可以从三个状态转移,删除第i个字符,删除第j个字符,修改第i个或第j个字符,分别对应f[i-1][j], f[i][j-1], f[i-1][j-1],取最小,然后+1。
时间复杂度
参考文献
Golang 代码
func minDistance(word1 string, word2 string) int {
slen1, slen2 := len(word1), len(word2)
f := make([][]int, slen1+1)
for i := range f {
f[i] = make([]int, slen2+1)
for j :=range f[i] {
f[i][j] = 1<<31 - 1
}
}
for i := 0; i <= slen1; i++ {
f[i][0] = i
}
for i := 0; i <= slen2; i++ {
f[0][i] = i
}
for i := 0; i < slen1; i++ {
for j := 0; j < slen2; j++ {
if word1[i] == word2[j] {
f[i+1][j+1] = f[i][j]
} else {
f[i+1][j+1] = min(min(f[i][j+1], f[i+1][j]), f[i][j]) + 1
}
}
}
return f[slen1][slen2]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}