LietCode
Palindrome Partitioning

Palindrome Partitioning

Abhi's photo
Abhi
·

3 min read

Explain the Problem

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example:

Input: s = "aab"

Output:

[
  ["a", "a", "b"],
  ["aa", "b"]
]

Awesome! Let's move on to the next step.

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

  1. Recursive Function: We'll create a helper function that tries to partition the string by checking every possible substring.

  2. Palindrome Check: If a substring is a palindrome, we add it to the current partition and recursively check the remaining substring.

  3. Backtracking: If we reach the end of the string, we add the current partition to the result list.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

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

  // Helper function to check if a string is a palindrome
  function isPalindrome(str, left, right) {
    while (left < right) {
      if (str[left] !== str[right]) {
        return false;
      }
      left++;
      right--;
    }
    return true;
  }

  // Helper function for backtracking
  function backtrack(start, path) {
    // If we've reached the end of the string, add the current partition to the result
    if (start === s.length) {
      result.push([...path]);
      return;
    }

    // Try every possible end index for the current substring
    for (let end = start; end < s.length; end++) {
      // Check if the substring s[start:end+1] is a palindrome
      if (isPalindrome(s, start, end)) {
        // If it is, add it to the current path
        path.push(s.substring(start, end + 1));
        // Recurse with the updated path
        backtrack(end + 1, path);
        // Backtrack: remove the last substring from the path
        path.pop();
      }
    }
  }

  // Start the backtracking with an empty path
  backtrack(0, []);

  return result;
}

Explanation of the Solution in Simple Terms

Imagine you have a string, and you want to divide it into parts such that each part reads the same forwards and backwards (like "racecar" or "level").

  • Recursive Function: This is like a helper that tries to cut the string into parts.

  • Palindrome Check: This means checking if a part of the string reads the same forwards and backwards.

  • Backtracking: This means if the current cut doesn't work, you go back and try a different cut.

For each part of the string, you check if it is a palindrome. If it is, you add it to your current partition and continue with the rest of the string. If you reach the end of the string, you've found a valid partition. If not, you undo your last cut and try another part.

Code Explanation in Pointers

  1. Initialize Result Array: Create an empty array to store all partitions.

  2. Define Palindrome Check: Create a function to check if a substring is a palindrome.

  3. Define Backtracking Function: Create a recursive function to explore different partitions.

  4. Base Case - End Reached: If the start index reaches the end of the string, add the current partition to the result.

  5. Loop Through Substrings: Try every possible end index for the current substring.

  6. Check Palindrome: If the substring is a palindrome, add it to the current path.

  7. Recursive Call: Call the function recursively with the updated path.

  8. Backtrack: Remove the last substring from the path before trying the next one.

  9. Start Search: Start the search with an empty path.

Complexity Analysis

  • Time Complexity: O(N * 2^N), where N is the length of the string. This is because we generate all possible partitions and check each one.

  • Space Complexity: O(N), due to the recursion stack and the path array.

backtracking