Description
Split a lowercase string into non-empty contiguous pieces so every piece reads the same forward and backward. Return all possible partitions, in any result order.
Solution
def partition(s):
n = len(s)
palindrome = [[False] * n for _ in range(n)]
for left in range(n - 1, -1, -1):
for right in range(left, n):
palindrome[left][right] = s[left] == s[right] and (right - left < 2 or palindrome[left + 1][right - 1])
result, path = [], []
def visit(start):
if start == n:
result.append(path.copy())
return
for end in range(start, n):
if palindrome[start][end]:
path.append(s[start:end + 1])
visit(end + 1)
path.pop()
visit(0)
return resultExamples
Example 1
- Input
["aab"]- Output
[["a","a","b"],["aa","b"]]
Either keep the two a characters separate or together.
Example 2
- Input
["a"]- Output
[["a"]]
One character is a palindrome.
Example 3
- Input
["aba"]- Output
[["a","b","a"],["aba"]]
The entire string is also a palindrome.
Approach
Precompute which substrings are palindromes using their endpoints and inner substring. Backtrack over possible next endpoints and accept only palindromic pieces.
Time & space
O(n^2 + n 2^n) time and O(n^2) auxiliary space excluding output, where n is the string length.