千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

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

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

发表于：2025-12-02 作者：千家信息网编辑
千家信息网最后更新 2025年12月02日，这篇文章主要介绍golang刷leetcode动态规划之如何编辑距离，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！给定两个单词 word1 和 word2，计算出将 word1
千家信息网最后更新 2025年12月02日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安全错误 数据库的锁怎样保障安全 windows服务器清缓存 公共网络安全的目的 远程登陆服务器设置 网络技术开发培训方案 为什么网络安全要学c语言 供应串口联网服务器公司 华为服务器mgmt管理 服务器 sas卡 美国金融交易数据库 网络安全视频教程教程 网络安全法规定 发生风险 如何不让360成为默认服务器 山西泉创网络技术有限公司 vb数据库的添加 软件开发中道德声明 软件开发电子书下载 数据库查询结论心得 软件开发属于哪大类 数据库tri 信息网络安全投稿周期 落实国庆网络安全保障工作报告 公共网络安全的目的 上海网络技术开发质量服务 网络技术公司的市场的环境分析 dns服务器怎么修复 武汉众生互联网科技有限公司 服务器机房安全规范 服务器统一管理设备 控制系统软件开发服务方案价钱 数据库课程设计中出现的问题

相关文章

0