Print all palindromic partitions of a string

Medium

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"]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}