動機

第一次看到DP比較慢

Problem

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

Input: s = abcOutput: 3Explanation: Three palindromic strings: a, b, c.

Example 2:

Input: s = aaaOutput: 6Explanation: Six palindromic strings: a, a, a, aa, aa, aaa.

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Sol1: DP

用DP看這個範圍是不是迴文，之後列舉

class Solution:
    @functools.cache
    def isPalin(self,i,j):
        if j-i < 0:
            return False
        elif j-i == 1 or j-i == 0:
            return True
        else:
            return (self.s[i] == self.s[j-1]) and self.isPalin(i+1,j-1)
    def countSubstrings(self, s: str) -> int:
        self.s = s
        ret = 0
        for l in range(1,len(s)+1):
            for i in range(len(s)):
                if i+l <= len(s) and self.isPalin(i,i+l):
                    ret += 1
        return ret

Sol2: expand

如果看一下時間複雜度，會發現DP解是O(n^2)

都平方，為什麼不直接從每一點往左右兩側展開，也都是O(n^2)

class Solution:
    def countSubstrings(self, s: str) -> int:
        def search(i,j):
            ret = 0
            while 0 <= i and j < len(s) and s[i] == s[j]:
                ret += 1
                i -= 1
                j += 1
            return ret
        ret = 0
        for i in range(len(s)):
            ret += search(i,i) + search(i,i+1)
        return ret