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"]
]
这道题的要求是切割字符串，使其每个字串都是回文，返回所有情形。
经典的回溯问题，变量i标识字符串的当前位置。接下来，j从i开始，直到结束，逐个判断i和j之间的是否为回文，如果是，记录下来，并从j后一位开始递归切割。
递归结束条件，就是i等于字符串长度。
时间复杂度：O(???)
空间复杂度：O(???)
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
class Solution
{
vector<vector<string>> vvs;
public:
vector<vector<string>> partition(string s)
{
vector<string> vs;
partition(s, 0, vs);
return vvs;
}
private:
void partition(string &s, int i, vector<string> &vs)
{
if(i == s.size())
{
vvs.push_back(vs);
return;
}
for(int j = i; j < s.size(); ++ j)
if(isPalindrome(s, i, j))
{
vs.push_back(s.substr(i, j - i + 1));
partition(s, j + 1, vs);
vs.pop_back();
}
}
bool isPalindrome(string &s, int i, int j)
{
while(i < j)
if(s[i ++] != s[j --])
return false;
return true;
}
};