131. Palindrome Partitioning

[mengyushi]

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        '''
        Backtracking

        '''

        res = []
        N = len(s)
        for i in range(1,N+1):
            if s[:i] == s[:i][::-1]:
                # s[:i] is palindrome
                res+=[[s[:i]]+rest for rest in self.partition(s[i:])]

        if not res:
            return [[]]

        return res