647 Palindromic Substrings
647. Palindromic Substrings
题目: https://leetcode.com/problems/Palindromic-Substrings/
难度:
Medium
思路
这道题要求给定一个字符串中的所有回文子串的个数，所以我想到了Manacher算法， Manacher算法
Manacher算法增加两个辅助变量id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界。得到一个很重要的结论：
- 如果mx > i，那么P[i] >= Min(P[2 * id - i], mx - i) . 为什么这样说呢，下面解释
下面，令j = 2*id - i，也就是说j是i关于id的对称点。
-
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于i和j对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有P[i] = P[j]；
-
当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，再具体匹配。
所以P[i] >= Min(P[2 * id - i], mx - i)，因为以j为中心的绘回文子串的左边界可能会比mx关于id的对称点要大，此时只能证明P[i]=P[2 * id - i] - 此外，对于 mx <= i 的情况，因为无法对 P[i]做更多的假设，只能让P[i] = 1，然后再去匹配。 此题还可以借鉴我leetcode第5题的解析， thining-in-lc-5
这道题的基本思想是将以每一个字符为中心的回文子串个数相加，还是用一个小例子来解释
其实，以‘#’为中心的回文子串就代表这个子串的长度是偶数，类似于'abba'这种
但是其实这个字符本身也是一个回文子串，所以叠加的形式是count += (P[i]+1)/2，为什么呢，以下是解释：
- 对于每一个以字符‘#’为中心的回文子串，其P值绝对是偶数，所以(P[i]+1)/2 = P[i]/2，并不影响
- 对于每一个以非字符‘#’为中心的回文子串，其P值绝对是奇数，这就保证了单个字母的回文子串(例如'a'也算一个回文子串)也被加起来了，因为(P[i]+1)/2 = P[i]/2+1
class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: str
"""
def preProcess(s):
if not s:
return ['^', '$']
T = ['^']
for c in s:
T += ['#', c]
T += ['#', '$']
return T
T = preProcess(s)
P = [0] * len(T)
id, mx, count = 0, 0, 0
for i in range(1,len(T) - 1):
j = 2*id - i
if mx > i:
P[i] = min(mx - i, P[j])
else:
P[i] = 0
while T[i+P[i]+1] == T[i-P[i]-1]:
P[i] += 1
if (i + P[i]) > mx:
id, mx = i, i + P[i]
for i in range(len(P)):
count += (P[i]+1)/2
return count
python无敌啊！！！有没有天理啊，手动滑稽😏😏😏😏！一行解法：
class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
return sum(len(os.path.commonprefix((s[:i][::-1], s[i:])))
+ len(os.path.commonprefix((s[:i][::-1], s[i + 1:]))) + 1
for i in range(len(s)))
解释下为啥要加两次，因为回文串有以下两种形式： - ‘abcba’ - 'abba'
那为啥要加那个1呢，上面解释过了，单个字符也算是一个回文子串呀，嘻嘻😁
