Palindrome Partitioning

Problem

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.

Solution Approach

Expected Time complexity: $O(n^2)$

Click - to see solution code

C++

class Solution {
    int n;
    string w;
    vector<string> arr;
    vector<vector<string>> ans;

   public:
    void partition(int indx) {
        if (indx == n) {
            ans.push_back(arr);
            return;
        }
        string s = "", ss;
        for (int j = indx; j < n; j++) {
            s.push_back(w[j]);
            ss = s;
            reverse(ss.begin(), ss.end());
            if (ss == s) {
                arr.push_back(s);
                partition(j + 1);
                arr.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        this->n = s.length();
        this->w = s;
        partition(0);
        return ans;
    }
};