[LeetCode] 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.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

class Solution {
    void helper(string &s, vector<vector<bool>>& P, int start, 
            vector<string> & vec, vector<vector<string>> &res)
    {
        if(start == s.length()) res.push_back(vec);
        for(int i=start; i< s.length(); i++)
        {
            if(P[start][i])
            {
                vec.push_back(s.substr(start, i-start+1));
                helper(s, P, i+1, vec, res);
                vec.pop_back();
            }
        }
    }
public:
    vector<vector<string>> partition(string s) 
    {
        int len = s.length();
        vector<vector<bool>> P(len, vector<bool>(len, false));
        for(int i=len-1;i>=0;i--)
        {
            for(int j=i;j<len;j++)
            {
                if(s[i] == s[j] && (j-i<2 || P[i+1][j-1]))
                {
                    P[i][j] = true;
                }
            }
        }
        vector<vector<string>> res;
        vector<string> vec;
        helper(s, P, 0, vec, res);
        return  res;
    }
};