C++ recursive solution exact


#1

bool isPlayndrom(string s)
{
if (s == “”) return true;
int i = 0;
int j = s.size()-1;

while (i < j)
{
if (s[i++] != s[j–]) return false;
}
return true;
}

vector<vector > Solution::partition(string A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
vector<vector > result;
if (A.size() == 0) return result;

int part_size = 1;

while (part_size <= A.size())
{
    string part1 = A.substr(0, part_size);
    if (isPlayndrom(part1))
    {
        string rest = A.substr(part_size);
        
        if (rest.size() > 0) {
            vector<vector<string> > other_part = partition(rest);

            for (auto v : other_part)
            {
                v.insert(v.begin(), part1);
                result.push_back(v);
            }        
        }
        else
        {
            vector<string> tmp = {part1};
            result.push_back(tmp);
        }
    }
    
    ++part_size ;
}

return result;

}