題目出處

647. Palindromic Substrings

難度

medium

個人範例程式碼 – DFS (會 TLE)

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        return self.dfs(s, 0)

    def dfs(self, s, start):
        # end of recursion
        if start >= len(s):
            return 0

        ans = 0
        # define
        for end in range(start, len(s)):
            if self.is_palindromic(s[start:end+1]):
                ans += 1

        # split 
        return ans + self.dfs(s, start+1)

    def is_palindromic(self, s):
        # print(s)

        start = 0
        end = len(s)-1
        while start <= end:
            if s[start] == s[end]:
                start += 1
                end -= 1
            else:
                return False

        return True

算法說明

DFS 的作法，應該會是最直覺地把所有可能性都舉出來，
總共會花大約 O(2^n) 的時間，會造成 TLE

input handling

一同在 DFS 內處理

Boundary conditions

在 DFS 內處理，發現 start >= end 時 return

個人範例程式碼 – DP

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        length = len(s)

        dp = [[0 for start in range(length)] for end in range(length)]

        for start in range(length):
            for end in range(start, length):
                # print(start, end)
                if dp[start][end]: # already recorded
                    ans += 1
                    continue

                if self.is_palindromic(s[start:end+1]):
                    ans += 1
                    tmp_start, tmp_end = start, end
                    while tmp_start <= tmp_end:
                        dp[tmp_start][tmp_end] = 1
                        tmp_start += 1
                        tmp_end -= 1

        return ans

    def is_palindromic(self, s):
        # print(s)

        start = 0
        end = len(s)-1
        while start <= end:
            if s[start] == s[end]:
                start += 1
                end -= 1
            else:
                return False

        return True

算法說明

在上方，我們知道 DFS 因為需要 O(2^n) 的運算時間會造成 TLE 後，
我們只好採取更快的策略，最直覺的我們會想到 DP

因為 DP 最擅長幫我們把解題時間從 O(2^n) 優化至 O(n^2) 的時間。

而要讓題目優化至 O(n^2) 時間，
我們就先建立一個 start, end 的二維查詢表。

我們更新的方式也很簡單，
如果當發現 dp[i][j] 是 palindrome，那也表示 dp[i+1][j-1] 也是 palindrome，直到 start > end，
因此我們可以劃出上圖的紅色斜線，

判斷時，我們初始化都是 0，如果之後發現已經被改成 1，
即可 continue 直接 pass 計算。

input handling

一同在 DP 內處理

Boundary conditions

兩層 DP 的 for 迴圈，
分別代表著 start, end

Reference

• 回文子串 · Palindromic Substrings