描述

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.

解析

根据题意，暴力破解，直接用双重循环，将各种组合都判断一次，时间复杂度为 O(N^2)，空间复杂度为 O(1)。

解答

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = 0
        for i in range(len(s)):
            for j in range(i+1,len(s)+1):
                if s[i:j] == s[i:j][::-1]:
                    count += 1
        return count

运行结果

Runtime: 752 ms, faster than 9.08% of Python online submissions for Palindromic Substrings.
Memory Usage: 11.9 MB, less than 39.45% of Python online submissions for Palindromic Substrings.

解析

根据题意，另一种思路比较巧妙，在从左到右遍历字符串的同时，以每个字符为中心，向两边扩展开来判断各种可能成为回文数的组合，时间复杂度为 O(N^2)，空间复杂度为 O(1)。

解答

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = 0
        for i in xrange(len(s)):
            #自身是回文数
            count += 1
            #回文长度是奇数的情况
            left = i - 1
            right = i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
            #回文长度是偶数的情况
            left = i
            right = i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                count += 1
                left -= 1
                right += 1
        return count

运行结果

Runtime: 100 ms, faster than 75.24% of Python online submissions for Palindromic Substrings.
Memory Usage: 11.8 MB, less than 74.94% of Python online submissions for Palindromic Substrings.

解析

根据题意，再有一种思路就是动态规划，单个字符是回文；两个连续字符如果相等是回文；如果有3个以上的字符，需要两头相等并且去掉首尾之后依然是回文。时间复杂度为 O(N^2)，空间复杂度为 O(1)。

解答

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        N = len(s)
        count = 0
        dp = [[0]*N for _ in range(N)]
        for j in range(N):
            for i in range(j):
                dp[i][j] = (s[i]==s[j]) & (dp[i+1][j-1] | (j-i<2) ) 
                if dp[i][j]:
                        count += 1
            dp[j][j] = 1
            #自身是回文数
            count += 1
        return count

运行结果

Runtime: 320 ms, faster than 29.55% of Python online submissions for Palindromic Substrings.
Memory Usage: 19.5 MB, less than 18.12% of Python online submissions for Palindromic Substrings.

每日格言：常常是最终一把钥匙打开了门。