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"]]

Problem Link

Recursion Tree

Code

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> temp;
        
        func(res,temp,s,0);
        return res;
    }
    
    void func(vector<vector<string>> &res,vector<string> &temp,string s,int start)
    {
        if(start==s.size())
            res.push_back(temp);
        for(int i=start;i<s.size();i++)
        {
            string str = s.substr(start,i-start+1);
            if(!isPallindrome(str))
                continue; //consider a greater length string
            temp.push_back(str);
            func(res,temp,s,i+1);
            temp.pop_back();
        }
    }
    bool isPallindrome(string str)
    {
        int n = str.size();
        
        for(int i=0,j=n-1;i<n/2;i++,j--)
        {
            if(str[i]!=str[j])
                return false;
        }
        return true;
    }
};

class Solution {
public:
vector<vector<string>> res;
    vector<vector<string>> partition(string s) {

        int n = s.size();

        vector<vector<int>> isP(n,vector<int>(n,1));

        for(int gap=0;gap<n;gap++) {
            for(int i=0,j=gap;j<n;i++,j++) {
                if(i==j) {
                    isP[i][j] = 1;
                } else {
                    isP[i][j] = s[i]!=s[j] ? 0 : isP[i+1][j-1];
                }
            }
        }

        vector<string> temp;

        solve(s,isP,temp,0);

        return res;

        

        
    }

    void solve(string &s, vector<vector<int>> &isP,vector<string> &temp,int start) {

        if(start>=s.size()) {
            res.push_back(temp);
            return;
        }
        
        for(int i=start;i<s.size();i++) {
            if(isP[start][i]) {
                temp.push_back(s.substr(start,i-start+1));
                solve(s,isP,temp,i+1);
                temp.pop_back();
            }
        }

    } 

    
};