锐客网

  1. 首页 > 睿知 > it技术 > >

阿里巴巴笔试题 -- 动态规划实现两个字符串的最短编辑记录

IT知识阿里巴巴笔试题

努力尽今夕，少年犹可夸。这篇文章主要讲述阿里巴巴笔试题 -- 动态规划实现两个字符串的最短编辑记录相关的知识，希望能为你提供帮助。


【阿里巴巴笔试题 -- 动态规划实现两个字符串的最短编辑记录】

阿里巴巴笔试题 -- 动态规划实现两个字符串的最短编辑记录

文章图片

一、题目说明什么是最短编辑距离呢？假定有两个字符串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();


//如果第二个字符串是空，直接返回第一个字符串的长度，操作为插入第一个字符串的个数

    推荐阅读


    上一篇：微信小游戏开发实战11:使用本地缓存

    下一篇：分分钟理解组合模式