JS实现计算最少回文切割数

作者注:算法能力一直是程序猿最基础也是最重要的一项基础能力,记得Pascal之父、结构化程序设计的先驱Niklaus Wirth最著名的一本书,书名叫作《算法 + 数据结构 = 程序》,算法与数据结构之于程序设计的重要性不言自明,作者本身也非常注重基础算法能力的培养,除了平常阅读一些算法书籍如《算法导论》、《算法》《数据结构与算法Java语言描述》外,也非常关注一些公众号提供的有关算法的描述跟讲解,但是这些算法的描述一般都是只会给出一些伪代码或者思路。我的公众号里我会不定期的对一些常见算法做讲解,并用js语言实现出来,共读者参考~

----------- 正文分割线 ---------

题目重现:

对一个字符串按照回文进行分割,例如ababbbabbababa就是字符串ababbbabbababa的一个回文分割,每一个字串都是一个回文。请找到可以分割的最少的字串数。例如:

ababbbabbababa最少4个字符串,分割三次:ababbbabbababa

如果字符串整体是回文,则需要0次分割,最少1个字符串

实现思路:

我们的基本思路是这样:首先,找出所有的回文子串(见下面分析),然后找出所有可以对整个字符串进行回文分割的实现方案,最后我们从这些所有可行方案中找出切割术最少的方案(可能不只一种)即为我们想要的结果。我们一步步来详细分析。

回文子串的查找

该如何更好的判断回文呢?我们设定P[i][j]:

为true时,表示str[i..j]为回文

为false时,表示str[i..j]不是回文

则,当:

i==j时,P[i][j]=true

j==i+1时,P[i][j]=str[i]==str[i]

其他,P[i][j]=P[i+1][j-1]&&(str[i]==str[j])

这个P该如何构建呢?根据其状态转移的方程,P[i][j]所代表的字符串,长度从1开始变化,逐渐到整个字符串,是这样的一个构建的过程,所以外层循环应该是所要判断的字串的长度。基本代码如下:

js代码实现如下:

我们以符号"_"来分割开始和结束位置,比如从字符串的第二个字符到第5个字符是个子回文,那么上述函数返回的结果中属性'2_5'为TRUE,否则为false.

获取所有的回文分割可行方案

这里的实现方案比较多,比如对所有的回文子串创建树结构,对树进行广度优先遍历,找到最浅的遍历方案的等。我结合了js语言的特性,运用hash来进行处理。当然也可以考虑用数组实现。思路如下:

我们可以获取所有的单个字符开头的回文子串的数组,并组装成一个hash,然后对hash进行遍历,在另一个对象中(或以数组实现也可),找到以当前遍历属性(以"_"分隔)的开始值减一为结尾的所有属性组成数组,再将当前属性链接上去,最终该对象的所有属性值都是实现回文分割的解决方案。最后,我们只需要再次遍历数组,找到所有切割数最少的方案即可。

所有代码

所有的代码实现如下。其中可能还有可以优化的地方,可再仔细琢磨一下。

本文来自企鹅号 - 从前端er到全栈er媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

位运算实用指南

说明 : 想来这应该是初次接触移位操作符时一定会了解到的知识点,根据2进制的整数表示方法应该不难理解,原因细节不再赘述~

7110
来自专栏算法修养

接口和多态性

如果你又加了一个百度外卖,那么eat函数中又要new 一个BaiDu() ,给开发带来麻烦。我们希望的是,如果代码要扩展了,那么代码要尽最大可能的进行很小的改动...

9530
来自专栏带你撸出一手好代码

JavaScript消除游戏实现思路讲解

之前讲解过一款JavaScript贪食蛇游戏详细的设计与实现,但是以那种方式进行描述 , 整篇文章会显得复杂冗长,除非深入细致的阅读和思考,否则文中内容并不容易...

39750
来自专栏Python小屋

微课系列(四):Python中map对象的几种用法和注意事项

在Python中,map、filter、enumerate、zip、reversed等对象除了惰性求值之外,还有个共同的特点是“其中的元素只能使用一次”,这一点...

9120
来自专栏AI派

Numpy 修炼之道 (13)—— 将python函数向量化

想要实现将python函数向量化,Numpy中的vectorize 和frompyfunc函数都可以满足要求。

45270
来自专栏苦逼的码农

从零打卡leetcode之day 1--两数之和

不过心里才两个循环时间复杂度可是n的平方,心想肯定得超时,不过还是大胆提交一下提交,呵呵,居然通过了。。。。

12910
来自专栏数据结构与算法

P1823 音乐会的等待

题目描述 N个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。队列中任意两个人A和B,如果他们是相邻或他们之间没有人比...

398130
来自专栏小詹同学

【记录帖】从零打卡刷Leetcode——No.007

小詹此记录贴的读者越来越少了,也许是小詹总结的不够好欢迎留言区提出宝贵的意见!也欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一...

13730
来自专栏web前端教室

【视频】- 5分钟学习<函数式编程>

温馨提示:视频请点此观看 // 视频文字版: JavaScript 函数式编程是一个存在了很久的话题, 现在ES6语法对于函数式编程更为友好,所以开始变的更...

25260
来自专栏WeaponZhi

轻松初探 Python 篇(五)—dict 和 set 知识汇总

这是「AI 学习之路」的第 5 篇,「Python 学习」的第 5 篇 dict dict 是 Python 内置的字典类型,熟悉 Java 的同学可以把它类比...

31790

扫码关注云+社区

领取腾讯云代金券