Skip to content

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呢，上面解释过了，单个字符也算是一个回文子串呀，嘻嘻😁

回到顶部