Problem description:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: “aab”
Output:

1
2
3
4
[
  ["aa","b"],
  ["a","a","b"]
]

Solution:

This is a similar backtracking problem. For this kind of question, we’ll use a helper function to help us check every possible sequence meet the requirement or not. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<vector<string>> partition(string s) {
        /*
        1. a sub function to check is palindrome or not
        */
        vector<vector<string>> res;
        vector<string> tmp;
        helper(res, tmp, s, 0);
        return res;
    }
    
    void helper(vector<vector<string>>& res, vector<string>& tmp, string s, int start){
        if(start== s.length()){
            res.push_back(tmp);
            return;
        } 
        
        for(int i= start; i< s.length(); i++){
            if(ispalin(s, start, i)){
                tmp.push_back(s.substr(start, i-start+1));
                helper(res, tmp, s, i+1);
                tmp.pop_back();
            }
        }
    }
    
    bool ispalin(string s, int start, int end){
        
        while(start<= end){
            if(s[start++] != s[end--]){
                return false;
            }
        }
        return true;
    }
};

time complexity: O(n*n!)

reference:
https://goo.gl/bBS1Eh