千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

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

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

发表于：2024-11-19 作者：千家信息网编辑
千家信息网最后更新 2024年11月19日，这篇文章主要介绍golang刷leetcode动态规划之如何编辑距离，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！给定两个单词 word1 和 word2，计算出将 word1
千家信息网最后更新 2024年11月19日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安全错误 数据库的锁怎样保障安全 连接多个数据库事务配置 网络安全对全球的影响 数据库标签控件图标 绍兴越淘网络技术有限公司手机 计算机网络技术重点考纲 大连云鼎软件开发 网络安全知识培训文章 美国1号服务器 密码 物理学专业转软件开发 湖南数据网络技术优势 分布式数据库面临的技术问题 德惠品质网络技术咨询诚信合作 定西飘允网络技术有限公司 回家法律法规数据库 互联网科技大数据信息分类 dns好用的服务器 第四版数据库第四章答案 计算机网络技术专业文案 数据库系统概论王珊电子版教材 西安智园软件开发有限公司 有网络安全专业的高校 云服务器root 如何看数据库状态对不对 公安网络安全学院分数线 长春软件开发web培训 计算机网络技术的工作日常 计算机网络包括网络安全么 惠普服务器没有识别磁盘 网络安全png 计算机网络技术制作网站

相关文章

0