Skip to content

Latest commit

 

History

History
118 lines (92 loc) · 4.66 KB

647._Palindromic_Substrings.md

File metadata and controls

118 lines (92 loc) · 4.66 KB

647. Palindromic Substrings

难度: Medium

刷题内容

原题连接

内容描述


Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
The input string length won't exceed 1000.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

思路

这道题要求给定一个字符串中的所有回文子串的个数，所以我想到了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

思路 2

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