golang刷leetcode动态规划（10）编辑距离
golang刷leetcode动态规划（10）编辑距离
golangLeetcode
发布于 2022-08-02 17:31:11
发布于 2022-08-02 17:31:11
文章被收录于专栏：golang算法架构leetcode技术php
给定两个单词 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')解题思路：
编辑距离又称levenshtein距离，用来衡量两个字符串的相似度，假设俩字符串分别为word1和word2，用m[i][j]存word1[0:i],word2[0:j]（左闭右开）的编辑距离，对于i,和j位置编辑距离m[i+1][j+1]；
1，如果word1[i]==word2[j],则编辑距离是
A，m[i][j]，word1[0:i],word2[0:j]（左闭右开）的编辑距离
B，m[i][j+1]+1，word1[0:i],word2[0:j＋1]（左闭右开）的编辑距离
C，m[i+1][j]+1，word1[0:i＋1],word2[0:j]（左闭右开）的编辑距离
这3种情况下最小者
2，如果word1[i]!=word2[j],则编辑距离是
上述3个分支中，A替换为m[i][j]＋1
3，由于m[i+1][j+1]用到了m[i][j+1]，m[i+1][j]，m[i][j]，所以采用递增循环。
4，初始条件，为了便于初始化，我们这里有个优化技巧：在word1和word2之前加一个空格，则：
A，m[0][0]=0
B，m[i][0]=i
C，m[0][j]=j
func minDistance(word1 string, word2 string) int {
if word1==""{
return len(word2)
}
if word2==""{
return len(word1)
}
m:=make([][]int,len(word1)+1)
for i:=0;i<len(word1)+1;i++{
m[i]=make([]int,len(word2)+1)
}
for i:=1;i<len(word1)+1;i++{
m[i][0]=i
}
for j:=1;j<len(word2)+1;j++{
m[0][j]=j
}
for i:=1;i<len(word1)+1;i++{
for j:=1;j<len(word2)+1;j++{
diff:=0
if word1[i-1]!=word2[j-1]{
diff=1
}
m[i][j]=min3(m[i-1][j]+1,m[i][j-1]+1,m[i-1][j-1]+diff)
}
}
return m[len(word1)][len(word2)]
}
func min3(a,b,c int)int{
if a<=b && a<=c{
return a
}
if b<=a&&b<=c{
return b
}
return c
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
腾讯云开发者
