131. Palindrome Partitioning

Question: Palindrome Partitioning

Solution

想法：先把所有的 substring 找出來後，再檢查他是不是 Palindrome

Palindrome 可以參考這一篇：125. Valid Palindrome

for loop 找出所有 substring:

例如 substring = “aab”

• i = 0: [”a”] 是 palindrome，才往下檢查 [”a”, “b”] 或是 [”ab”] -> DFS
  • 檢查 [”a”, “b”]
    • 檢查 [”a”] 是 palindrome
      • 檢查 [”b”] V（一種可能）[”a”, “a”, “b”]
  • 檢查 [”ab”] X
• i = 1: [”aa”] 是 palindrome，往下檢查 ["b"] -> DFS
  • 檢查 [”b”] V （一種可能）[”aa”, “b”]
• i = 2: [”aab”] 是 palindrome V（一種可能）[”aab”]

以下提供兩種 substring 寫法

1. word 字串切割

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        res = list()
        subs = list()
        def dfs(sub):
            if not sub:
                res.append(subs.copy())
                return
        
            for i in range(len(sub)):
                if self.is_palindrome(sub[:i + 1]):
                    subs.append(sub[:i + 1])
                    dfs(sub[i + 1:])
                    subs.pop()
        dfs(s)
        return res
    def is_palindrome(self, substring):
        head, tail = 0, len(substring) - 1
        while head < tail:
            if substring[head] != substring[tail]:
                return False
            head += 1
            tail -= 1
        return True

2. index，dfs 變成收 index 參數

def dfs(j):
    if j == len(s):
        res.append(subs.copy())
        return
        
    for i in range(j, len(s)):
        if self.is_palindrome(s[j:i + 1]):
            subs.append(s[j:i + 1])
            dfs(i + 1)
            subs.pop()
dfs(0)
return res

Video Solution