[Day9]-[动态规划] 编辑距离
作者:方勇(gopher)
- 2022 年 4 月 08 日
本文字数:814 字
阅读完需:约 3 分钟
![[Day9]-[动态规划]编辑距离](https://static001.geekbang.org/infoq/58/58c0c18c069128da0b989f8a193445c4.png)
72. 编辑距离
给你两个单词 word1
和 word2
, 请返回将 word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
复制代码
示例 2:
输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
复制代码
提示:
0 <= word1.length, word2.length <= 500
word1
和word2
由小写英文字母组成
题解:
func minDistance(word1 string, word2 string) int {
var min func(x, y int) int // 最小值
var solution func(s1, s2 string) int // 解决方案
min = func(x, y int) int {
if x < y {
return x
}
return y
}
solution = func(s1, s2 string) int {
m, n := len(s1), len(s2) // 两个字符串的长度
var dp = make([][]int, m+1) // dpTable dp[0][i] 和 dp[j][0] 为基态数据
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1) // 初始化二维数据带零值
dp[i][0] = i // 初始化基态数据
}
for j := 0; j <= n; j++ {
dp[0][j] = j
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if s1[i-1] == s2[j-1] { // 从字符串的第1个字符开始比较
dp[i][j] = dp[i-1][j-1] // 如果相等 编辑距离不变
} else {
// 取插入,删除,替换 的最小距离+1
dp[i][j] = min(dp[i][j-1]+1, min(dp[i-1][j]+1, dp[i-1][j-1]+1))
}
}
}
// 终态就是 两个字符串都分析完了
return dp[m][n]
}
return solution(word1,word2)
}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 2
![用户头像](http://static001.geekbang.org/account/avatar/00/13/b1/81/13f23d1e.jpg?x-oss-process=image/resize,w_200,h_200)
方勇(gopher)
关注
Dead or Alive. 生存战斗是知识的源泉! 2018.11.08 加入
我是一名SRE哨兵,目前是好大夫基础架构部高级工程师。专注于 SRE,微服务、中间件的稳定性和可用性建设,整体负责好大夫服务治理云平台的设计和搭建!
评论