Palindrome Partitioning

Problem Statement

Given a string s, split s into substrings where every substring is a palindrome. Return all possible lists of palindromic substrings.

You may return the solution in any order.

Example 1:

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"

Output: [["a"]]

Constraints:

1 <= s.length <= 20
s contains only lowercase English letters.

You should aim for a solution with O(n \cdot (2^n)) time and O(n) space, where n is the length of the input string.

Recommended Time and Space Complexity

You should aim for a solution with O(n \cdot (2^n)) time and O(n) space, where n is the length of the input string.

Hint 1

For a given string there are 2^n possible partitions because at each index we have two decisions: we can either partition and start a new string, or continue without partitioning. Can you think of an algorithm to recursively traverse all combinations?

Hint 2

We can use backtracking to recursively traverse the string with indices j (start of the current substring) and i (current iterating index). At each step, we either skip partitioning at the current index or, if the substring from j to i is a palindrome, make a partition, update j = i + 1, and start a new substring. The base condition to stop the recursion is when j reaches the end of the string. How do you implement this?

Hint 3

We start with j = 0, i = 0 and a temporary list which stores the substrings from the partitions. Then we recursively iterate the string with the index i. At each step we apply the 2 decisions accordingly. At the base condition of the recursive path, we make a copy of the current partition list and add it to the result.

Solution

Backtracking (Pick / Not Pick)

def partition(s: str) -> list[list[str]]:
    res, part = [], []

    def dfs(j, i):
        if i >= len(s):
            if i == j:
                res.append(part.copy())
            return

        if is_palindrome(s, j, i):
            part.append(s[j : i + 1])
            dfs(i + 1, i + 1)
            part.pop()

        dfs(j, i + 1)

    def is_palindrome(s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l, r = l + 1, r - 1
        return True

    dfs(0, 0)
    return res

Time complexity: O(n \cdot 2 ^ n) Space complexity: O(n)

Backtracking

def partition(s: str) -> list[list[str]]:
    res, part = [], []

    def dfs(i):
        if i >= len(s):
            res.append(part.copy())
            return
        for j in range(i, len(s)):
            if is_palindrome(s, i, j):
                part.append(s[i : j + 1])
                dfs(j + 1)
                part.pop()

    def is_palindrome(s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l, r = l + 1, r - 1
        return True

    dfs(0)
    return res

Time complexity: O(n \cdot 2 ^ n) Space complexity: O(n)

Backtracking (DP)

def partition(s: str) -> list[list[str]]:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for l in range(1, n + 1):
        for i in range(n - l + 1):
            dp[i][i + l - 1] = (s[i] == s[i + l - 1] and
                                (i + 1 > (i + l - 2) or
                                dp[i + 1][i + l - 2]))

    res, part = [], []
    def dfs(i):
        if i >= len(s):
            res.append(part.copy())
            return
        for j in range(i, len(s)):
            if dp[i][j]:
                part.append(s[i : j + 1])
                dfs(j + 1)
                part.pop()

    dfs(0)
    return res

Time complexity: O(n \cdot 2 ^ n) Space complexity: O(n ^ 2)

Recursion

def partition(s: str) -> list[list[str]]:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for l in range(1, n + 1):
        for i in range(n - l + 1):
            dp[i][i + l - 1] = (s[i] == s[i + l - 1] and
                                (i + 1 > (i + l - 2) or
                                dp[i + 1][i + l - 2]))

    def dfs(i):
        if i >= n:
            return [[]]

        ret = []
        for j in range(i, n):
            if dp[i][j]:
                nxt = dfs(j + 1)
                for part in nxt:
                    cur = [s[i : j + 1]] + part
                    ret.append(cur)
        return ret

    return dfs(0)

Time complexity: O(n \cdot 2 ^ n) Space complexity: O(n ^ 2)