美文网首页
647. Palindromic Substrings 回文子串

647. Palindromic Substrings 回文子串

作者: 这就是一个随意的名字 | 来源:发表于2017-07-30 08:53 被阅读0次

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.

思路
【回文中心法】
定义当前扫描点i为扫描的回文中心,向两端发散扫描并统计有效的回文串个数。
此种从中间到两边的扫描判定避免了将aaa、aba、区别对待的情形,但是要注意考虑回文串长度为奇数(aaa)和偶数(aaaa)的情况。
时间复杂度O(n^2)。

public class Solution {
    int count = 0;
   
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
       
        for (int i = 0; i < s.length(); i++) { // i is the mid point
            extendPalindrome(s, i, i); // odd length;
            extendPalindrome(s, i, i + 1); // even length
        }
       
        return count;
    }
   
    private void extendPalindrome(String s, int left, int right) {
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++; left--; right++;
        }
    }
}
class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n=len(s)
        ans=0
        for center in xrange(2*n-1):
            left=center/2
            right=left+(center%2)
            while left>=0 and right<n and s[left]==s[right]:
                ans+=1
                left-=1
                right+=1
        return ans

【Manacher's Algorithm 马拉车算法】
算法说明

def countSubstrings(self, S):
    def manachers(S):
        A = '@#' + '#'.join(S) + '#$'
        Z = [0] * len(A)
        center = right = 0
        for i in xrange(1, len(A) - 1):
            if i < right:
                Z[i] = min(right - i, Z[2 * center - i])
            while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
                Z[i] += 1
            if i + Z[i] > right:
                center, right = i, i + Z[i]
        return Z

    return sum((v+1)/2 for v in manachers(S))

相关文章

网友评论

      本文标题:647. Palindromic Substrings 回文子串

      本文链接:https://www.haomeiwen.com/subject/pfehlxtx.html