Partition A String Into Set(s) Of All Palindromic substrings



Program for partitioning a string into all palindromic subsets.

#include<iostream>
#include<vector>

using namespace std;

// Check if a given string is palindrome.
bool IsPalin (string str) {
    int left = 0;
    int right = str.size() - 1;
    while (left < right) {
        if (str.at(left) == str.at(right)){
            left++, right--;
        } else {
            return false;
        }
    }
    return true;
}

// Store all palindromic sets in result.
void Palindromic_Sets (string s, vector<string>& vec,
                                 vector<vector<string>>& result) {
    if (s.length()==0) {
        result.push_back(vec);
    } else {
        for (int i=0; i < s.size(); i++) {
            string prefix = s.substr(0, i+1);
            if (IsPalin(prefix)) {
                vec.push_back(prefix);
                Palindromic_Sets(s.substr(i+1), vec, result);
                vec.pop_back();
            }                 
        }
    }
}

int main() {

    string str("ababa");
    vector<vector<string>> result;
    vector<string> vec;

    Palindromic_Sets(str, vec, result);
    for (auto& vec : result) {
        for (auto& str : vec) {
            cout << "[" << str << "] ";
        } cout << endl;
    }
    return 0;
}

Output

[a] [b] [a] [b] [a] 
[a] [b] [aba] 
[a] [bab] [a] 
[aba] [b] [a] 
[ababa] 



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.