📢📢📢📣📣📣

哈喽！大家好，我是【Bug 终结者】 ，【CSDN新星创作者】🏆，阿里云技术博主🏆，51CTO人气博主🏆，INfoQ写作专家🏆

一位上进心十足，拥有极强学习力的【Java领域博主】😜😜😜

🏅【Bug 终结者】博客的领域是【面向后端技术】的学习，未来会持续更新更多的【后端技术】以及【学习心得】。 偶尔会分享些前端基础知识，会更新实战项目，面向企业级开发应用！
🏅 如果有对【后端技术】、【前端领域】感兴趣的【小可爱】，欢迎关注【Bug 终结者】💞💞💞

❤️❤️❤️ 感谢各位大可爱小可爱！ ❤️❤️❤️

目录

• 一、题目说明
• 二、思路分析
• 三、递归实现
• • ♻️核心源码
  • ⏰效果图
  • ⚠️递归实现的缺点
• 四、递归+动态规划实现
• • ♻️核心源码
  • ⏰效果图
  • ✅递归+动态规划的好处
• ⛵小结

一、题目说明

什么是最短编辑距离呢？假定有两个字符串s1和s2，允许对字符串进行以下三种操作：

1. 插入一个字符

2. 删除一个字符

3. 替换一个字符

将字符串s1转换成字符串s2的最少操作次数就是字符串s1和字符串s2之间的最短编辑距离。两个字符串的最短编辑距离越短，意味着两个字符串越相似。

时间复杂度：O(m*n)

空间复杂度：O(m*n)

二、思路分析

下图为分析

上图可以看到，第一个字符串经过 新增、删除、修改后变为第二个字符串

例：

String str1 = "ABC";String str2 = "BBC"//我们经过以下操作将str1替换为str2"ABC" --> "ABC" // 删除字符 B 即可

三、递归实现

♻️核心源码

package com.wanshi.test;import org.junit.Test;public class Test4 {    @Test    public void test() { String str1 = "ABC"; String str2 = "BBC"; long start = System.currentTimeMillis(); int res = ld(str1, str2); long end = System.currentTimeMillis(); System.out.println(res); System.out.println("运算时间：" + (end - start));    }    /**     * 计算最短编辑距离     * @param str1  第一个字符串     * @param str2  第二个字符串     * @return  最短编辑距离次数     */    private int ld(String str1, String str2) { //如果内容相同了，直接返回即可，无操作 if (str1.equalsIgnoreCase(str2)) {     return 0; } //如果第一个字符串是空，直接返回第二个字符串的长度，操作为插入第二个字符串的个数 if (str1.equalsIgnoreCase("")) {     return str2.length(); } //如果第二个字符串是空，直接返回第一个字符串的长度，操作为插入第一个字符串的个数 if (str2.equalsIgnoreCase("")) {     return str1.length(); } int ldRes = 0; //截取出两个字符串的第一个字符 String str1Last = str1.substring(0, 1); String str2Last = str2.substring(0, 1); //截取后面的字符 String str1Content = str1.substring(1); String str2Content = str2.substring(1); //如果相同就进入下一次计算 if (str1Last.equalsIgnoreCase(str2Last)) {     ldRes = ld(str1Content, str2Content); } else {     //判断3次计算结果那次运算结果最少，就返回哪一个     String strInsert = str1Last + str2;     String strReplace = str1Last + str2Content;     String strDel = str2Content;     int ldInsert = ld(str1, strInsert);     int ldReplace = ld(str1, strReplace);     int ldDel = ld(str1, strDel);     //获取三个操作中最短的编辑次数     ldRes = Math.min(ldInsert, Math.min(ldReplace, ldDel)) + 1; } return ldRes;    }}

⏰效果图

⚠️递归实现的缺点

我们把两个字符串换为以下字符

String str1 = "最小编辑机双向停机短信提醒及距离是把一个字符串";String str2 = "关小编辑机双向停机短信提醒及优化出账时间的需求";

再次执行查看

跑到最后我笔记本风扇刷刷的！

不敢再跑下去了，性能实在是太低了！

我的笔记本 4+16的，速度算快的了，可还是因为在执行期间风扇一直转！

下面我们优化代码，这个代码必须优化，真的是性能太低太低！

为什么会这么慢呢？

第一我们的字符串太长，然后我们又是使用的递归计算，递归计算就是**一层一层往下走，然后一层一层往上返，执行步骤极多，导致一直出不来结果，所以需要优化代码**！

四、递归+动态规划实现

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

动态规划的好处就是：可以大大提高系统的性能，使程序得到非常显著的性能提升！

♻️核心源码

package com.wanshi.test;import org.junit.Test;import java.util.HashMap;import java.util.Map;public class Test3 {    @Test    public void t1() { String str1 = "最小编辑机双向停机短信提醒及距离是把一个字符串"; String str2 = "关小编辑机双向停机短信提醒及优化出账时间的需求"; Map<String, Integer> ldMap = new HashMap<>(); long start = System.currentTimeMillis(); int res = ld(str1, str2, ldMap); long end = System.currentTimeMillis(); System.out.println(res); System.out.println("运算时间：" + (end - start));    }    /**     * 计算最短编辑距离     * @param str1  第一个字符串     * @param str2  第二个字符串     * @param ldMap map缓存     * @return  最短编辑距离次数     */    private int ld(String str1, String str2, Map<String, Integer> ldMap) { //如果内容相同了，直接返回即可，无操作 if (str1.equalsIgnoreCase(str2)) {     return 0; } //如果第一个字符串是空，直接返回第二个字符串的长度，操作为插入第二个字符串的个数 if (str1.equalsIgnoreCase("")) {     return str2.length(); } //如果第二个字符串是空，直接返回第一个字符串的长度，操作为插入第一个字符串的个数 if (str2.equalsIgnoreCase("")) {     return str1.length(); } //键名 String strKey = str1 + "_" +str2; //如果map中存在该key，直接返回即可 if (ldMap.containsKey(strKey)) {     return ldMap.get(strKey); } int ldRes = 0; //截取出两个字符串的第一个字符 String str1Last = str1.substring(0, 1); String str2Last = str2.substring(0, 1); //截取后面的字符 String str12 = str1.substring(1); String str22 = str2.substring(1); //如果相同就进入下一次计算 if (str1Last.equalsIgnoreCase(str2Last)) {     ldRes = ld(str12, str22, ldMap); } else {     //判断3次计算结果那次运算结果最少，就返回哪一个     int ldInsert = ld(str1, (str1Last + str2), ldMap);     int ldReplace = ld(str1, (str1Last + str22), ldMap);     int ldDel = ld(str1, str22, ldMap);     //获取三个操作中最短的编辑次数     ldRes = Math.min(ldInsert, Math.min(ldReplace, ldDel)) + 1; } //存入map缓存，提高性能 if (!ldMap.containsKey(strKey)) {     ldMap.put(strKey, ldRes); } return ldRes;    }}

⏰效果图

✅递归+动态规划的好处

我们可以看到，只用递归实现跑这个跑的电脑差点爆炸，我们采用动态规划的方式优化代码后，性能瞬间就上来了，可见动态规划的好处！

提升了程序的性能，增加可用性，增强了程序的健壮性！

⛵小结

以上就是【Bug 终结者】对两个字符串的最短编辑记录简单的概述，本题为阿里巴巴笔试题，动态规划是常见的考题类型，所以说，大家要掌握好动态规划，合理的在系统中使用会极大的提高系统的性能！

如果这篇【文章】有帮助到你，希望可以给【Bug 终结者】点个赞👍，创作不易，如果有对【后端技术】、【前端领域】感兴趣的小可爱，也欢迎关注❤️❤️❤️ 【Bug 终结者】❤️❤️❤️，我将会给你带来巨大的【收获与惊喜】💝💝💝！

书法艺术字体