Palindrome Partitioning Medium 0 attempts
LeetCode ↗

Palindrome Partitioning

Medium BacktrackingRecursion LeetCode

Given a string s, split it into pieces so that every piece is itself a palindrome, and return every way of partitioning the string that achieves this.

A palindrome is a sequence that reads identically in both directions. Each partitioning must account for every character of s exactly once, with no characters skipped or reused.

Input Format
Implement partition(s). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]

Example 2

Input
s = "a"
Output
[["a"]]
Constraints
  • 1 <= s.length <= 16
  • s consists of lowercase English letters
Test Cases (2)
Case 1
Args: ["aab"] Expected: [["a","a","b"],["aa","b"]]
Case 2
Args: ["a"] Expected: [["a"]]
Topics
BacktrackingRecursion

Use backtracking. At each index, try every possible prefix — if the prefix is a palindrome, add it to the current partition and recurse on the remainder. When the index reaches the end of the string, save the partition.

javascript
function partition(s) {
  const result = [];

  function isPalindrome(str, left, right) {
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left++;
      right--;
    }
    return true;
  }

  function backtrack(start, current) {
    if (start === s.length) {
      result.push([...current]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (isPalindrome(s, start, end)) {
        current.push(s.substring(start, end + 1));
        backtrack(end + 1, current);
        current.pop();
      }
    }
  }

  backtrack(0, []);
  return result;
}

Time: O(n * 2^n) — there are 2^(n-1) ways to partition the string, and checking palindromes takes O(n). Space: O(n) for recursion depth.

Saved in this browser only. Private to you.

JavaScript