Palindrome Partitioning

Problem

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 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.

Pattern

String, Dynamic Programming, Backtracking

Approaches

Backtracking

Code

def partition(s: str) -> list[list[str]]:
    partitions = []

    def backtrack(partition, i):

        if i == len(s):
            partitions.append(partition)

        for j in range(i + 1, len(s) + 1):
            t = s[i:j]
            if t == t[::-1]:
                backtrack(partition + [t], j)

    backtrack([], 0)
    return partitions

Test

>>> from palindrome_partitioning__backtracking import partition
>>> sorted(partition("aab"))
[['a', 'a', 'b'], ['aa', 'b']]
>>> partition("a")
[['a']]

palindrome_partitioning__backtracking.partition(s: str) → list[list[str]]