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

Dynamic Programming.

I used vector<vector<string>> dp[s.size()] as dynamic programming array.

dp[i] stores all the possible palindrome partitioning of s[0] ~ s[i]. So dp[s.size()] is the value we need to return finally.

dp[i] = dp[j – 1] appends s[j] ~ s[i], if string s[j] ~ s[i] is palindrome., j = from 0 to i .

dp[-1] is empty.

class Solution {
public:
    vector<vector<string>> partition(string s) {
        if(s.size() == 0) return vector<vector<string>>();
        vector<vector<string>> dp[s.size()];
        //base condition
        vector<string> vStr;
        vStr.push_back(s.substr(0, 1));
        dp[0].push_back(vStr);
        //dynamic programmming
        for(size_t i = 1; i < s.size(); i++){
            for(size_t j = i; j > 0; j--){
                string tmps = s.substr(j, i - j + 1);
                if(isPalindrome(tmps)){
                    for(auto it = dp[j - 1].begin(); it != dp[j - 1].end(); it++){
                        //append character s[i] to dp[i - 1]
                        vStr = *it;
                        vStr.push_back(tmps);
                        dp[i].push_back(vStr);
                    }
                }   
            }
            //j == 0
            string tmps = s.substr(0, i + 1);
            if(isPalindrome(tmps)){
                vStr.clear();
                vStr.push_back(tmps);
                dp[i].push_back(vStr);
            }
        }
        return dp[s.size() - 1];
    }
    bool isPalindrome(string s){
        //o(n)
        //extreme case
        if(s.size() == 1) return true;
        int i, j;
        if(s.size() % 2 == 0){
            //even
            i = s.size() / 2 - 1;
            j = i + 1;
        }
        else{
            //odd
            i = s.size() / 2 - 1;
            j = i + 2;
        }
        while(i >= 0){
            if(s[i] != s[j]) return false;
            i--;
            j++;
        }
        return true;
    }
};