Palindrome Partitioning — Step-by-Step Visualization

Algorithm Pattern

Backtracking with Pruning

Key Idea

We use backtracking to explore all possible ways to partition the string. At each step, we pick a substring starting from the current index. If that substring is a palindrome, we add it to our current partition and recursively process the rest of the string. If we reach the end of the string, the current partition is a valid solution.

Step-by-Step Approach

1. Define a recursive function `dfs(index, currentPartition)`.
2. If `index == len(s)`, add `currentPartition` to the results.
3. Iterate through possible end indices `j` for the current substring.
4. If `s[index...j]` is a palindrome, recurse with `dfs(j + 1, currentPartition + [s[index...j]])`.

Common Gotchas

• Checking palindromes repeatedly can be slow; for very long strings, precomputing palindrome status with 2D DP is optimization, but for most test cases, a simple check suffices.