千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

导航： 首页 > 互联网科技 >

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

发表于：2026-11-03 作者：千家信息网编辑
千家信息网最后更新 2026年11月03日，这篇文章主要介绍golang刷leetcode动态规划之如何编辑距离，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！给定两个单词 word1 和 word2，计算出将 word1
千家信息网最后更新 2026年11月03日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动态规划之如何编辑距离"这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注行业资讯频道！

很赞哦！
字符 动态 规划 两个 内容 单词 字符串 示例 篇文章 解释 输入 输出 最小 相似 价值 位置 兴趣 分支 初始条件 又称 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 互联网科技海报 百单网互联网科技有限公司怎么样 互联网科技网 科技互联网企业 新华互联网科技学校 互联网和科技技术 互联网属科技 杭州互联网科技公司 电子科技大学互联网 上海致骋互联网科技 新浪科技互联网 长亮科技互联网金融 互联网科技有限公司 翻译 武汉健翔互联网络科技有限公司 2021互联网科技公司排名 云南省自由互联网科技有限公司 郑州欣桑互联网科技有限公司 科技互联网经济论坛 北京瑞云互联网科技有限公司 株洲百竞科技的互联网营销顾问 涨乐互联网科技 鸠鸠互联网科技 上海挚品互联网科技 群盈汇互联网科技有限公司 广州富喜互联网络科技 城市宝互联网科技有限公司 神州科技互联网有限公司 云鲸互联网络科技有限公司 互联网对科技影响 武汉亿视互联网科技有限公司

相关文章

0