Problem Statement

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

LeetCode

• https://leetcode.com/problems/palindrome-partitioning/description/

Constraints

1 <= s.length <= 16
s contains only lowercase English letters.

• For the recursive approach:
  • n = 16, 2^16: 65536, which is acceptable for backtracking with pruning.

Examples

Example 1:

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

Explanation:
There are two ways to partition the string such that each substring is a palindrome:
"a" | "a" | "b"
"aa" | "b"

Example 2:

Input: s = "a"
Output: [
         ["a"]
        ]

Explanation: The only possible partition is the string itself, as it is already a palindrome.

Example 3:

Input: s = "racecar"
Output: [
          [ "r", "a", "c", "e", "c", "a", "r" ],
          [ "r", "aceca", "r" ],
          [ "racecar" ]
         ]

Explanation:
Possible palindrome partitions:
"r" | "a" | "c" | "e" | "c" | "a" | "r"
"r" | "aceca" | "r"
"racecar"

Different Approaches

1️⃣ Backtracking

The key intuition here is:

1. Recursive Exploration: For each starting index in the string, we check every possible ending index to see if the substring is a palindrome.
2. Backtracking: If the substring is a palindrome, we include it in the current partition and recursively explore the remaining substring. When the partition reaches the end of the string, we add it to the result.
3. Backtrack to Explore More Options: After adding a valid partition to the result, we backtrack by removing the last substring and continuing with other possible partitions.

Code:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    // Helper function to check if a substring is a palindrome
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // Backtracking function to find all palindrome partitions
    void backtrack(int start, const string& s, vector<string>& currentPartition, vector<vector<string>>& result) {
        // Base case: if we have reached the end of the string, add the current partition to the result
        if (start == s.size()) {
            result.push_back(currentPartition);
            return;
        }

        // Explore all possible end positions for the current substring
        for (int end = start; end < s.size(); end++) {
            if (isPalindrome(s, start, end)) {  // Only proceed if it's a palindrome
                // Choose the substring
                currentPartition.push_back(s.substr(start, end - start + 1));
                
                // Explore further partitions with the updated start position
                backtrack(end + 1, s, currentPartition, result);
                
                // Backtrack to explore other options
                currentPartition.pop_back();
            }
        }
    }

    // Main function to initiate the partitioning process
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> currentPartition;
        backtrack(0, s, currentPartition, result);
        return result;
    }
};

// Helper function to print the result
void printPartitions(const vector<vector<string>>& partitions) {
    for (const auto& partition : partitions) {
        cout << "[ ";
        for (const string& str : partition) {
            cout << "\"" << str << "\" ";
        }
        cout << "]";
    }
    cout << endl;
}

int main() {
    Solution solution;
    string s = "aab";
    vector<vector<string>> partitions = solution.partition(s);

    cout << "Palindrome partitions of \"" << s << "\":" << endl;
    printPartitions(partitions);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2^n), due to the exponential number of possible partitions.
• Space Complexity: O(n), for the recursion stack