【LeetCode】647. Palindromic Substrings 解题报告（Python）

标签： LeetCode

---

题目地址：https://leetcode.com/problems/palindromic-substrings/description/

题目描述：

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.

题目大意

找出字符串中的回文子串数目。

解题方法

动态规划。

这个回文字符串的题母，千篇一律啊。在5. Longest Palindromic Substring中，当遇到回文字符串时，我们是使用maxL记录下来最长的那个。稍微修改，这个题我们只要做统计个数就可以。因此代码基本一样。

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

二刷—

两边扩散法。。待续

日期

2018 年 3 月 15 日 –雾霾消散，春光明媚