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进行遍历,在另一个对象中(或以数组实现也可),找到以当前遍历属性(以"_"分隔)的开始值减一为结尾的所有属性组成数组,再将当前属性链接上去,最终该对象的所有属性值都是实现回文分割的解决方案。最后,我们只需要再次遍历数组,找到所有切割数最少的方案即可。

所有代码

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

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20171223G0RT9Z00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券