Question

How to split a string into palindromic segments, where each segment is a palindrome in C++

Answer 1

#include <iostream>
#include <vector>

using std::vector;
using std::string;

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> path;
        backtrack(0, s, path, res);
        
        return res;
    }

    void backtrack(int start, string &s, vector<string> &path,
                   vector<vector<string>> &res) {
        if (start == s.size()) {
            res.push_back(path);
            return;
        }

        for (int i = start; i < s.size(); i++) {
            if (isPalindrome(s, start, i)) {
                path.push_back(s.substr(start, i - start + 1));
                backtrack(i + 1, s, path, res);
                path.pop_back();
            }
        }
    }

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

int main() {
    Solution sol;
    string s = "rotor";
    auto result = sol.partition(s);

    for (auto &vec : result) {
        std::cout << "[ ";
        for (auto &p : vec) std::cout << "\"" << p << "\" ";
        std::cout << "]\n";
    }
    
    s = "level";
    result = sol.partition(s);

    for (auto &vec : result) {
        std::cout << "[ ";
        for (auto &p : vec) std::cout << "\"" << p << "\" ";
        std::cout << "]\n";
    }
    
    s = "abba";
    result = sol.partition(s);

    for (auto &vec : result) {
        std::cout << "[ ";
        for (auto &p : vec) std::cout << "\"" << p << "\" ";
        std::cout << "]\n";
    }
}


/*
run:

[ "r" "o" "t" "o" "r" ]
[ "r" "oto" "r" ]
[ "rotor" ]
[ "l" "e" "v" "e" "l" ]
[ "l" "eve" "l" ]
[ "level" ]
[ "a" "b" "b" "a" ]
[ "a" "bb" "a" ]
[ "abba" ]

*/

 

70+ SQL courses for beginners and professionals