131. Palindrome Partitioning - python3

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

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

보자마자 backtracking 을 생각했지만 아직도 제대로 이해 못해서인지 혼자 힘으로 절대 못푸는듯..^^

그래서 답을 봤읍니다.

Solution 1: Runtime: 628 ms - 64.90% / Memory Usage: 26.7 MB - 59.77%

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        self.backtrack(s, start=0, path=[], res=res)
        return res

    def backtrack(self, s, start, path, res):
        if start == len(s):
            res.append(path)
            return

        for end in range(start + 1, len(s) + 1):
            sub = s[start: end]
            if sub == sub[::-1]:    #isPalindrome
                self.backtrack(s, end, path + [sub], res)

palindrome 이면 backtrack 재귀
end 값을 다음 start 값으로 넘겨준다

재귀는 상상디버깅 넘 어렵네요..;