131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

Solution:
Consider to use DSF. The "end condition" or "basic case" is when the search reaches the end of the string. Also need to determine whether all the possible substrings are palindrome or not.

Code:

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        if(!s.size()) return res;
        vector<string> temp;
        vector<vector<bool>> isP(s.size(), vector<bool>(s.size(), false));
        for(int i=s.size()-1; i>=0; --i){//DP for judging palindrome;
            for(int j=i; j<s.size(); ++j){
                if(s[i]==s[j] && (j-i<=2 || isP[i+1][j-1])) isP[i][j] = true;
            }
        }
        pDSF(s, 0, temp, isP, res);
        return res;
    }
private:
    void pDSF(string s, int ind, vector<string> &t, vector<vector<bool>> &isP, vector<vector<string>> &r){
        if(ind == s.size()) r.push_back(t);
        else{
            for(int i=ind; i<s.size(); ++i){
                if(isP[ind][i]){
                    t.push_back(s.substr(ind, i+1-ind));
                    pDSF(s, i+1, t, isP, r);
                    t.pop_back();
                }
            }
        }
    }
};