leetcode131. Palindrome Partitio

原题链接https://leetcode.com/problems/palindrome-partitioning/

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        
        def isPalindrome(s):
            # n = len(s)
            # if len(s) <= 1:
            #     return True
            # for i in range((n + 1) // 2):
            #     if s[i] != s[n-1-i]:
            #         return False
            # return True
            return s == s[::-1]
        
        def backtrack(path,s):
            if not s:
                res.append(path[:])
                return
            for i in range(len(s)):
                if isPalindrome(s[:i+1]):
                    path.append(s[:i+1])
                    backtrack(path,s[i+1:])
                    path.pop()
        res = []
        path = []
        backtrack(path,s)
        return res