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 =
Return
"aab"
,Return
[ ["aa","b"], ["a","a","b"] ]
[Thoughts]
这种需要输出所有结果的基本上都是DFS的解法。实现如下。
[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: }
No comments:
Post a Comment