131. Palindrome Partitioning

Medium

---

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.

Example 1:

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

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

• 1 <= s.length <= 16

• s contains only lowercase English letters.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        self.dfs(s, 0, result, [])
        return result
    
    def dfs(self,string, start= 0, result = [], l = []):
        if start >= len(string):
            result.append(l[:])
        for index in range(start, len(string)):
            if self.plaindrome(string[start:index+1]):
                l.append(string[start:index+1])
                self.dfs(string, index+1, result, l)
                l.pop()

    def plaindrome(self, string):
        return string == string[::-1]