Print all palindromic partitions of a string
Problem
Split the string into pieces so that every piece is a palindrome. Return every such split.
Example 1
Input: "aab" Output: [["a","a","b"], ["aa","b"]]
Also asked as: Print all palindromic partitions of a string
Test cases
Case 1
Input: "aab" Expected (any order): [["a","a","b"],["aa","b"]]
Case 2
Input: "a" Expected (any order): [["a"]]
Case 3
Input: "aba" Expected (any order): [["a","b","a"],["aba"]]
View solutionHide solution1 approach
1. Backtrack over cut positions
Time O(2ⁿ · n)Space O(n)
For each prefix that is a palindrome, add it to the current partition and recurse on the rest.
function partitionPalindromes(s) { const res = [], path = []; const isPal = (l, r) => { while (l < r) if (s[l++] !== s[r--]) return false; return true; }; const bt = (start) => { if (start === s.length) { res.push([...path]); return; } for (let end = start; end < s.length; end++) { if (isPal(start, end)) { path.push(s.slice(start, end + 1)); bt(end + 1); path.pop(); } } }; bt(0); return res;}