5.Palindrome Partitioning

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

Example 2:
Input: s = "a"
Output: [["a"]]

Solution: (Backtracking)

Approach: * Splitting string at every possible point * If Left substring is palindrome checking it recursively for right substring

class Solution
{
public:
    bool isPalen(string s)
    {
        int i = 0;
        int l = s.length() - 1;

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

    void subsetPartion(string s, vector<vector<string>> &res, vector<string> &v)
    {

        int n = s.length();

        if (n == 0)
        {
            res.push_back(v);
            return;
        }

        for (int i = 1; i <= s.length(); i++)
        {
            string ls = s.substr(0, i);
            string rs = s.substr(i, n - i);
            if (isPalen(ls))
            {
                v.push_back(ls);
                subsetPartion(rs, res, v);
                v.pop_back();
            }
        }

        return;
    }

    vector<vector<string>> partition(string s)
    {
        vector<vector<string>> res;
        vector<string> v;
        subsetPartion(s, res, v);
        return res;
    }
};