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

所有代码

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