131. Palindrome Partitioning

Typical backtracking (or DFS) problem. In each DFS function, we'll check the substring of length [1, s.size()-start+1]. The termination condition will be start == s.size().

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> partition(string s) {  
4:      vector<vector<string>> res;  
5:      vector<string> sol;  
6:      helper(0, s, sol, res);  
7:      return res;  
8:    }  
9:    bool isPalindrome(string s) {  
10:      int i = 0, j = s.size()-1;  
11:      while (i < j) {  
12:        if (s[i] != s[j]) return false;  
13:        i++; j--;  
14:      }  
15:      return true;  
16:    }  
17:    void helper(int start, string s, vector<string> &sol, vector<vector<string>> &res) {  
18:      if (start == s.size()) {  
19:        res.push_back(sol);  
20:        return;  
21:      }  
22:      for (int i = start; i < s.size(); i++) {  
23:        string ss = s.substr(start, i-start+1);  
24:        if (isPalindrome(ss)) {  
25:          sol.push_back(ss);  
26:          helper(i+1, s, sol, res);  
27:          sol.pop_back();  
28:        }  
29:      }  
30:      return;  
31:    }  
32:  };