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 {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> p;
        if(!s.empty()){
            dfs(s, 0, p, res);
        }
        return res;
    }
private:
//判断字符串从from到to是否为回文
    bool isPalindrome(const string &s, int from, int to){
        while(from < to){
            if(s[from++] != s[to--]) return false;
        }

        return true;
    }

    void dfs(const string &str, int pos, vector<string> &path, vector<vector<string>> &ret){
        int n = str.size();
        if(pos == n){
            ret.push_back(path);
            return;
        }

        for(int i = pos; i < n; i++){
            if(isPalindrome(str, pos, i)){
                path.push_back(str.substr(pos, i - pos + 1));
                dfs(str, i + 1, path, ret);
                path.pop_back();
            }
        }
    }
};