中心扩散法Python实现

中心扩散法Python实现

中心扩散法经常用在回文字串上，回文字串是指从头读和倒过来读顺序一样的字符串，比如 ‘aba’，‘cgagc’ 等等，单个字符’a’也是回文字串。

一个回文串可能有多个回文子串，比如回文串’cgagc’，它的回文子串有’c’、‘g’、‘a’、‘g’、‘c’、‘gag’，当然，一个并不是回文串的字符串也可以有回文子串。

中心扩散法顾名思义就是从中心开始向两边扩散，与暴力求解法不同的是，中心扩散法是从第一个字符开始，作为中心（指针开始处），设置向左和向右的指针，如果左指针和右指针指向的字符相同，那么就找到了一个回文串，左指针和右指针再分别向左向右扩散一步，再次比较两指针指向的字符是否相同…一直向外扩散，直到左指针和右指针指向的字符不同或者有一个指针到达字符串边界；然后将原字符串的第二个字符作为中心，进行扩散，直到最后一个字符。

这样就找出一个字符串所包含的所有回文串了。

需要注意的是，有时候字符串会是这种情况’acbbcb’，即有两个相同字符连续，此时’bb’也是一个回文子串，但是如果只使用上面的方法是没有办法找到的，这时需要用到双数中心，即使用两个相邻的字符作为中心进行扩散，比如以‘ac’为中心，以’cb’为中心，…，遍历一遍后就可以找出所有的重复字符串。

前面说的以一个字符为中心的叫做单数中心。

下面举两个Leetcode中的例子，第一个是求一个字符串的的回文子串数量，比如对于字符串’acbabccaba’，要求它的回文子串数量。

这样的题目一般都可以使用暴力法两个for循环解决，但是运行时间和内存占用很大，另外也可以使用滑动窗口，使用中心扩散法用python实现如下：

#注意以双数中心遍历的时候的边界为len(s)-1

第二个是求一个字符串的最长回文子串，也可以使用中心扩散法，python实现如下：

这一题的思想是将所有回文子串保存在一个列表a中，最后使用max(a,key=len)语句求a中长度最大的回文子串。

从上面的程序可以看出，中心扩散法相比于暴力法，复杂度要低很多。