The problem
A palindrome reads the same forwards and backwards, like aba. Given a string s, return every way to cut it into pieces that are all palindromes, in any order.
Examples
01
- Input
s = "aab"
- Output
[["a", "a", "b"], ["aa", "b"]]
02
- Input
s = "a"
- Output
[["a"]]
Constraints
- 1 ≤ s.length ≤ 16
- Only lowercase English letters.
The idea
Cut from the left. The first piece is s[0..j] for some j, and it must be a palindrome; then cut the rest the same way. Every first piece that works is one branch of the search.
Checking a piece from scratch each time repeats work, so first fill a table: s[i..j] is a palindrome when its end letters match and its inside, s[i+1..j−1], is one (a piece of one or two matching letters needs no inside). Filling it from the end of the string backwards means the inside is always known first.
- Time
- O(n · 2ⁿ) — up to 2ⁿ⁻¹ ways to cut, each copied
- Space
- O(n²) — the table
Solution · every language run against every case
class Solution: def partition(self, s: str) -> List[List[str]]: n = len(s) # pal[i][j]: is s[i..j] a palindrome? Its ends match and its inside is one. pal = [[False] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i, n): pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1]) out, cur = [], [] def cut(i): # s[:i] is already cut into palindromes if i == n: out.append(cur[:]) return for j in range(i, n): if pal[i][j]: cur.append(s[i : j + 1]) cut(j + 1) cur.pop() cut(0) return out