Palindrome Partitioning - CPP Solution

1. Introduction

This blog post explores a fascinating string processing problem in C++ known as Palindrome Partitioning. The challenge is to partition a given string such that every substring of the partition is a palindrome. This problem is a great example of the use of backtracking and recursion in algorithm design.

Problem

Given a string s, the task is to partition s in such a way that every substring of the partition is a palindrome. We need to return all possible palindrome partitioning of s.

Example 1:

- Input: s = "aab"

- Output: [["a","a","b"],["aa","b"]]

Example 2:

- Input: s = "a"

- Output: [["a"]]

2. Solution Steps

1. Use backtracking to explore all possible partitions of the string.

2. Check if the current substring is a palindrome.

3. If it is, add it to the current partition and recurse for the remaining string.

4. Backtrack and try different partitions.

5. Store each valid partitioning that consists only of palindromes.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to check if a substring is a palindrome
bool isPalindrome(const string &s, int start, int end) {
    while (start < end) {
        if (s[start++] != s[end--]) return false;
    }
    return true;
}

// Helper function for backtracking
void backtrack(vector<vector<string>> &result, vector<string> &current, string &s, int start) {
    if (start >= s.length()) {
        result.push_back(current);
        return;
    }

    for (int end = start; end < s.length(); end++) {
        if (isPalindrome(s, start, end)) {
            current.push_back(s.substr(start, end - start + 1));
            backtrack(result, current, s, end + 1);
            current.pop_back(); // Backtrack
        }
    }
}

// Function to partition string into all possible palindrome partitioning
vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    vector<string> current;
    backtrack(result, current, s, 0);
    return result;
}

int main() {
    string s = "aab";
    vector<vector<string>> partitions = partition(s);
    cout << "Palindrome partitions:" << endl;
    for (const auto &part : partitions) {
        for (const string &str : part) {
            cout << str << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

Palindrome partitions:
a a b
aa b

Explanation:

1. The input string "aab" is used for generating palindrome partitions.

2. The function explores all substrings, checking for palindromes and partitioning accordingly.

3. For "aab", it finds two valid partitions: ["a", "a", "b"] and ["aa", "b"].

4. Each partition is a combination where every substring is a palindrome.

5. The use of backtracking allows the function to explore all possible partitions and collect those that satisfy the palindrome condition.