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

2年前 (2022) 程序员胖胖胖虎阿

229 0 0

📢📢📢📣📣📣

哈喽！大家好，我是【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;
    }

}