golang刷leetcode动态规划之如何编辑距离

这篇文章主要介绍golang刷leetcode动态规划之如何编辑距离,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

十余年品牌的成都网站建设公司,成百上千企业网站设计经验.价格合理,可准确把握网页设计诉求.提供定制网站建设、商城建设微信平台小程序开发成都响应式网站建设公司等服务,我们设计的作品屡获殊荣,是您值得信赖的专业网站设计公司。

给定两个单词 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        m[i]=make([]int,len(word2)+1)    }     for i:=1;i     m[i][0]=i     }      for j:=1;j      m[0][j]=j      }    for i:=1;i        for j:=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}

以上是“golang刷leetcode动态规划之如何编辑距离”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注创新互联行业资讯频道!


分享题目:golang刷leetcode动态规划之如何编辑距离
本文地址:http://myzitong.com/article/ieipso.html