647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/

solution

• 双指针: 中心扩散

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0
        for i in range(len(s)):
            res += self.palindromic(s, i, i)
            res += self.palindromic(s, i, i+1)
        return res

    def palindromic(self, s, i, j):
        temp_res = 0
        while i >=0 and j < len(s) and s[i] == s[j]:
            temp_res += 1
            i -= 1
            j += 1
        return temp_res

时间复杂度：O() 空间复杂度：O()

# 字符串dp: 注意二维dp和一维字符串性质一起对应起来, dp[i][j]：表示左闭右闭区间范围[i,j]的子串是否是回文子串

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False] * len(s) for _ in range(len(s))]
        result = 0
        for i in range(len(s)-1, -1, -1): # 注意遍历顺序
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    if j - i <= 1:
                        result += 1
                        dp[i][j] = True
                    elif dp[i+1][j-1]:
                        result += 1
                        dp[i][j] = True
        return result

时间复杂度：O() 空间复杂度：O()

follow up

回文类