647-palindromic-substrings.md

647. Palindromic Substrings - 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

1. 输入的字符串长度不会超过1000。

---

题目标签：String / Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

这道题的运行时间居然达到了2060ms，看来方法还是比较暴力，需要考虑更优的做法。

Language	Runtime	Memory
python3	2060 ms	N/A

class Solution:
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = [0, 1]
        if len(s) < 2:
            return dp[len(s)]
        else:
            for i in range(2, len(s)+1):
                dp.append(dp[i-1] + [s[:i][j:] == s[:i][j:][::-1] for j in range(i)].count(True))
            return dp[-1]