LeetCode 131 · Medium · Backtracking

Palindrome Partitioning

Given a string s, cut it into pieces so that every piece reads the same backwards, and return every way of doing so.

O(n · 2ⁿ)time
O(n)space besides the output
cut a palindrome prefixthen recurse on the rest

1–9 lowercase letters · capped at 120 tree nodes and 250 steps (a run of 7 equal letters already needs 128)

s with its cuts blue bars and letters = pieces already cut on this path · yellow = the candidate s[i..j]

part the pieces on the current path

decision tree node = the piece cut at that level · dashed = not a palindrome, pruned

res 0 partitions

private List<List<String>> res;private List<String> part;private String s;public List<List<String>> partition(String s) { this.s = s; res = new ArrayList<>(); part = new ArrayList<>(); dfs(0); return res;}private void dfs(int i) { if (i >= s.length()) { res.add(new ArrayList<>(part)); return; } for (int j = i; j < s.length(); j++) { if (isPali(s, i, j)) { part.add(s.substring(i, j + 1)); dfs(j + 1); part.remove(part.size() - 1); } }} private boolean isPali(String s, int l, int r) { while (l < r) { if (s.charAt(l) != s.charAt(r)) { return false; } l++; r--; } return true;}
i, j
—
substring(i, j+1)
—
part
[]
res.size()
0

Why it works

  1. Brute force tries all 2ⁿ⁻¹ cut patterns (each gap between letters is cut or not) and checks every piece. That is O(n · 2ⁿ) whether or not the pieces can work.
  2. Choose the first piece, then recurse. dfs(i) only needs to pick where the piece that starts at i ends. If s[i..j] is not a palindrome, no partition can start with it, so the whole subtree is pruned at once.
  3. Worst case is all one letter. Then every piece is a palindrome, all 2ⁿ⁻¹ patterns are answers, and each check plus copy costs O(n): O(n · 2ⁿ). The stack and part are at most n deep.
  4. Pitfall: off-by-one in the substring. The piece is s.substring(i, j + 1) and the next call is dfs(j + 1). Using j in either place re-reads a letter or skips one.
  5. Speed-up: precompute isPal[i][j] with the interval DP (s[i] == s[j] and isPal[i+1][j-1]) so each check is O(1). Palindrome Partitioning II (132) asks only for the fewest cuts and is pure DP.