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)