Skip to content

131. Palindrome Partitioning

Difficulty Topics

Description

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.

Solution

palindrome-partitioning.py
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        N = len(s)
        res = []

        def go(index, curr):
            if index == N:
                res.append(curr)
                return

            for j in range(index, N):
                x = s[index : j + 1]
                if x == x[::-1]:
                    go(j + 1, curr + [x])

        go(0, [])
        return res