📢📢📢📣📣📣
哈喽！大家好，我是【Bug 终结者】 ，【CSDN新星创作者】🏆，阿里云技术博主🏆，51CTO人气博主🏆，INfoQ写作专家🏆
一位上进心十足，拥有极强学习力的【Java领域博主】😜😜😜
🏅【Bug 终结者】博客的领域是【面向后端技术】的学习，未来会持续更新更多的【后端技术】以及【学习心得】。 偶尔会分享些前端基础知识，会更新实战项目，面向企业级开发应用！
🏅 如果有对【后端技术】、【前端领域】感兴趣的【小可爱】，欢迎关注【Bug 终结者】💞💞💞
❤️❤️❤️ 感谢各位大可爱小可爱！ ❤️❤️❤️
目录
- 一、题目说明
- 二、思路分析
- 三、递归实现
- ♻️核心源码
- ⏰效果图
- ⚠️递归实现的缺点
- 四、递归+动态规划实现
- ♻️核心源码
- ⏰效果图
- ✅递归+动态规划的好处
- ⛵小结
一、题目说明
什么是最短编辑距离呢？假定有两个字符串s1和s2，允许对字符串进行以下三种操作：
-
插入一个字符
-
删除一个字符
-
替换一个字符
将字符串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 终结者】❤️❤️❤️，我将会给你带来巨大的【收获与惊喜】💝💝💝！
