Palindrome partitioning (backtracking)

Medium TimeO(n · 2ⁿ) SpaceO(n) stack

Cut a string s into pieces so that every piece reads the same backwards, and return every way of doing it — 'aab' gives [a, a, b] and [aa, b]. The pieces are contiguous and, joined back together, give the original string. A single character counts as a palindrome, so at least one cutting always exists.

Examples

Example 1

Input
s = 'aab'
Output
[["a","a","b"],["aa","b"]]
aa is a palindrome so it may stay whole; ab is not, so b is always its own piece.

Example 2

Input
s = 'ab'
Output
[["a","b"]]
ab does not read the same backwards, so the only cutting is into single characters.

The Code

function isPalindrome(s) {
  let i = 0, j = s.length - 1;
  while (i < j) {
    if (s[i] !== s[j]) return false;
    i++;
    j--;
  }
  return true;
}
function backtrack(start, s, path, result) {
  if (start === s.length) {
    result.push(path.slice());
    return;
  }
  for (let end = start + 1; end <= s.length; end++) {
    const piece = s.slice(start, end);
    if (isPalindrome(piece)) {
      path.push(piece);
      backtrack(end, s, path, result);
      path.pop();
    }
  }
}
function partition(s) {
  const result = [];
  backtrack(0, s, [], result);
  return result;
}
partition('aab');
Done

The first 25 calls, of 31. This one does not fit on a page.

Step through partition('aab') call by call

More like this

All backtracking examples (10) →