Yang Shuqi

Palindromic Substrings

 

    647. Palindromic Substrings

    Solutions

    Solution 1:

    For each char in the string, there are 2 kinds of palindromic substring possible:

    1. odd substring

    2. even substring

    Expand from each char as a center for both odd and even substring.

    Solution 2: Manacher’s Algorithm Reference

    def countSubstrings(self, s):
    """
    :type s: str
    :rtype: int
    """
    A = '@#' + '#'.join(s) + '#$'
    S = [0] * len(A)
    center = 0
    right = 0
    
    for i in range(len(A)-1):
        if i < right:
            S[i] = min(S[2*center - i], right-i)
        
        while A[i+S[i]+1] == A[i-S[i]-1]:
            S[i] += 1
        if i+S[i] > right:
            center = i
            right = i + S[i]
            
    return sum((v+1)/2 for v in S)
    Search