131. Palindrome Partitioning

Problem Link

Description

---

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

 

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.

Solution

---

Python3

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        N = len(s)
        res = []
 
        def isPal(x):
            M = len(x)
            i, j = 0, M - 1
 
            while i <= j and x[i] == x[j]:
                i += 1
                j -= 1
            
            return i >= j
 
        def backtrack(index, curr):
            nonlocal res
 
            if index >= N:
                res.append(curr[:])
                return
            
            for j in range(index, N):
                if isPal(s[index: j + 1]):
                    curr.append(s[index : j + 1])
                    backtrack(j + 1, curr)
                    curr.pop()
 
        backtrack(0, [])
        return res