首页 » 运维 » 正文

leetcode647回文子串(Palindromic Substrings) python

最简单的方法,当然是找到所有的字符串,然后反转,然后判断反转后的字符串是否和原字符串相同(回文子串定义),相同的,计数器+1

既然这道题出现在leetcode肯定就不会推荐我们使用上边的暴力解法,那么我们来换个思路:

对于每个单独的字符来说,它都是一个回文子串,然后,回文子串可能是偶数:例如:

aa bb cc abba , 这样的是偶数的

也可能是奇数的,例如:

aba cbc cabac

这个地方有一个规律,

如果cabac是一个回文子串,那么它的特殊子集aba肯定也是一个回文子串

如果abba是一个回文子串,那么它的特殊子集bb也肯定是一个回文子串

这里的特殊子集就是回文子串的中心子集

我们可以通过如下思路来解决:

遍历所有元素, 然后遍历的过程中,以每个元素为中心,两边进行比较,如果所有的元素相同,那么就找到一个子串

例如,因为测试用例不太好明白,我们换一个字符串 abcbada

huiwen

 

首先我们从a开始:

a左边没有元素,也就是说以a元素为中心的不可能存在奇数的回文串,只可能存在偶数

a 与它的下一个元素b进行对比(这个时候a本身是left,下一个元素是right),发现 s[left] 不等于 s[ring],不成立,并且这个时候的left不能再左侧移动了(左侧没有元素了)

然后我们看b元素:

这个时候分两种情况,

以b为中心的回文子串为奇数的情况

这时候的left = a right=c 然后发现:  right 不等于left ,说明不存在这样的回文子串

以b为中心的回文子串为偶数的情况

这时候 left = b right=c 然后发现:  right 不等于 left ,结束

也就是以b为中心的回文子串不存在

然后继续下移,C元素:

以c为中心的回文子串为奇数的情况

这时候 left = b right=b 然后发现:  right =left 说明找到一个回文子串,这个时候我们不是结束,而是继续left左移,right右移,继续判断 left =a right = a 又找到一个….

 

代码如下:

代码部分参考:https://blog.csdn.net/fuxuemingzhu/article/details/79433960 

 

 

 

发表评论