Palindrome Partitioning medium

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.

A palindrome string is a string that reads the same backward as forward.

Example 1

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

Example 2

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

Steps

1. Backtracking: We will use a backtracking algorithm to explore all possible partitions. The core idea is to recursively try adding substrings to the current partition.

2. Palindrome Check: For each potential substring, we need a function to check if it's a palindrome. This can be done efficiently by comparing the characters from the beginning and end, moving inwards.

3. Base Case: The base case of our recursion is when we've reached the end of the input string. At this point, we add a copy of the current partition to the results.

4. Recursive Step: In the recursive step, we iterate through all possible positions to split the remaining string. For each split, we check if the substring up to the split point is a palindrome. If it is, we add it to the current partition and recursively call the function for the remaining part of the string. After the recursive call returns, we backtrack by removing the last added substring from the current partition. This ensures we explore all possible combinations.

Explanation

The backtracking algorithm systematically explores all possible ways to partition the string. The palindrome check ensures that only valid partitions (partitions consisting of only palindromes) are added to the final result. The backtracking mechanism is crucial to explore every possibility without modifying the original string during the process.

Code

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

using namespace std;

bool isPalindrome(const string& s, int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

void partitionHelper(const string& s, int index, vector<string>& currentPartition, vector<vector<string>>& result) {
    if (index == s.length()) {
        result.push_back(currentPartition);
        return;
    }

    for (int i = index; i < s.length(); ++i) {
        if (isPalindrome(s, index, i)) {
            currentPartition.push_back(s.substr(index, i - index + 1));
            partitionHelper(s, i + 1, currentPartition, result);
            currentPartition.pop_back(); // Backtrack
        }
    }
}


vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    vector<string> currentPartition;
    partitionHelper(s, 0, currentPartition, result);
    return result;
}

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

    for (const auto& partition : partitions) {
        cout << "[";
        for (size_t i = 0; i < partition.size(); ++i) {
            cout << "\"" << partition[i] << "\"";
            if (i < partition.size() - 1) {
                cout << ",";
            }
        }
        cout << "]" << endl;
    }
    return 0;
}

Complexity

• Time Complexity: O(N * 2^N), where N is the length of the string. In the worst case, we might need to explore all possible partitions, and the number of partitions can grow exponentially. The palindrome check within the loop takes O(N) in the worst case.

• Space Complexity: O(N * 2^N) in the worst case, primarily due to the space needed to store the resulting partitions. The recursive call stack can also contribute to the space complexity, but it's usually bounded by the depth of the recursion, which is at most N.