Palindrome Partitioning Visualizer & Step-by-Step Algorithm Solution

Partition a string such that every substring of the partition is a palindrome using backtracking and two-pointer palindrome validation.

Category: backtracking | Difficulty: Medium

Tags: Backtracking, Two Pointers, String, Recursion, Dynamic Programming

Palindrome Partitioning

[]
String "aab"
a
0
a
1
b
2
100%
state
saab
curr[]
partitionsFound0
length3
Initialization
1/55
Explanation

Start partition algorithm on string "aab" (length 3).

Source Code
1function partition(s: string): string[][] {
2 const result: string[][] = [];
3
4 function isPalindrome(s: string, left: number, right: number) {
5 while (left <= right) if (s[left++] !== s[right--]) return false;
6 return true;
7 }
8
9 function backtrack(curr: string[], start: number) {
10 if (start === s.length) {
11 result.push([...curr]);
12 return;
13 }
14
15 for (let end = start; end < s.length; end++) {
16 if (isPalindrome(s, start, end)) {
17 curr.push(s.slice(start, end + 1));
18 backtrack(curr, end + 1);
19 curr.pop();
20 }
21 }
22 }
23
24 backtrack([], 0);
25 return result;
26}