## Sunday, March 3, 2013

### [LeetCode] Palindrome Partitioning, Solution

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"]
]
```
» Solve this problem

[Thoughts]

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