Leetcode 131. Palindrome Partitioning

Seawolf

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]]:
        results = []
        
        def palindrome(left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        def dfs(start, result):
            if start >= len(s):
                results.append(result[:])
                return
            
            for i in range(start, len(s)):
                if palindrome(start, i):
                    result.append(s[start: i + 1])
                    dfs(i + 1, result)
                    result.pop(len(result) - 1)
        
        dfs(0, [])
        return results