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



回到顶部