[LeetCode] 647. Palindromic Substrings 回文子字符串

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 647. Palindromic Substrings 回文子字符串,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

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

Example 1:post

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

 

Example 2:this

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

 

Note:url

  1. The input string length won't exceed 1000.

给了一个字符串,计算有多少个回文子字符串,不一样index的都算做不一样的子字符串。htm

解法1: DPblog

解法2: Manacher's Algorithm字符串

Python: DPget

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        count = 0
        start, end, maxL = 0, 0, 0
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i):
                dp[j][i] = (s[j] == s[i]) & ((i - j < 2) | dp[j + 1][i - 1])
                if dp[j][i]:
                    count += 1
            dp[i][i] = 1
            count += 1
        return count

Python: Manacher's Algorithminput

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        def manacher(s):
            s = '^#' + '#'.join(s) + '#$'
            P = [0] * len(s)
            C, R = 0, 0
            for i in xrange(1, len(s) - 1):
                i_mirror = 2*C-i
                if R > i:
                    P[i] = min(R-i, P[i_mirror])
                while s[i+1+P[i]] == s[i-1-P[i]]:
                    P[i] += 1
                if i+P[i] > R:
                    C, R = i, i+P[i]
            return P
        return sum((max_len+1)/2 for max_len in manacher(s))

C++:

class Solution {
public:
    int countSubstrings(string s) {
        if (s.empty()) return 0;
        int n = s.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            helper(s, i, i, res);
            helper(s, i, i + 1, res);
        }
        return res;
    }
    void helper(string s, int i, int j, int& res) {
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            --i; ++j; ++res;
        }
    }
};

C++:

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), res = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) ++res;
            }
        }
        return res;
    }
};

  

相似题目:

[LeetCode] 5. Longest Palindromic Substring 最长回文子串

[LeetCode] 9. Palindrome Number 验证回文数字

[LeetCode] 125. Valid Palindrome 有效回文

[LeetCode] 516. Longest Palindromic Subsequence 最长回文子序列

  

All LeetCode Questions List 题目汇总