題目出處

131. Palindrome Partitioning

難度

medium

個人範例程式碼

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if not s:
            return []

        self.ans = []
        self.dfs(s, [], 0, len(s))
        return self.ans

    def dfs(self, s, partitions, start, end):
        # end of recursion
        if start >= end:
            self.ans.append(list(partitions))
            return

        # define and spliit
        for idx in range(start, end):
            split_s = s[start:idx+1] # least one word, max = [start:(end-1+1)] = [start:end]
            if self.is_palindrome(split_s):
                partitions.append(split_s)
                self.dfs(s, partitions, idx+1, end) # go next
                partitions.pop()

        return

    def is_palindrome(self, s):
        print(s)
        start = 0
        end = len(s)-1
        while(start <= end and s[start] == s[end]): 
            start += 1
            end -= 1
        else:
            if start <= end: # check
                return False
            else:
                return True

算法說明

組合類的變化題，使用 dfs，嘗試窮舉所有的組合。

• 由 start 開始，計算至 end
• 取 split 時記得要取 [start:idx+1] 才會是 start~idx
• 而往下走時，要指定的下一個座標也是 idx+1 (因為目前只判斷到包含 idx)

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

如果沒有 s，直接 return []

Boundary conditions

見上述說明

Reference

• 分割回文串 · Palindrome Partitioning