-
Notifications
You must be signed in to change notification settings - Fork 0
/
Palindrome_Partitioning.cpp
45 lines (40 loc) · 1.15 KB
/
Palindrome_Partitioning.cpp
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
38
39
40
41
42
43
44
45
// 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"]
// ]
class Solution {
public:
bool isPalindrome(const string &s) {
int size = s.size();
for (int i = 0; i < size/2; i++) {
if (s[i] != s[size-1-i])
return false;
}
return true;
}
void partition(string &s, int start, vector<vector<string> > &result,
vector<string> &item) {
if (start >= s.size()) {
result.push_back(item);
return;
}
for (int i = 1; start+i <= s.size(); i++) {
string str = s.substr(start, i);
if (isPalindrome(str)) {
item.push_back(str);
partition(s, start+i, result, item);
item.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string> > result;
vector<string> item;
partition(s, 0, result, item);
return result;
}
};