16
08/2015
[LeetCode] Palindrome Partitioning
Palindrome Partitioning
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"] ]
解题思路：
题意为找出对字符串的所有划分，使得每个划分都是回文。用递归的方法做。
注意s.substr(i);方法，如果i等于s的长度，返回一个空字符串。若i大于s的长度，报错。
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> item;
helper(item, s, result);
return result;
}
void helper(vector<string>& item, string s, vector<vector<string>>& result){
int len = s.length();
if(len == 0 && item.size()>0){
result.push_back(item);
return;
}
for(int i=0; i<len; i++){
string s1 = s.substr(0, i + 1);
if(isPalindrome(s1)){
item.push_back(s1);
helper(item, s.substr(i + 1), result);
item.pop_back();
}
}
}
bool isPalindrome(string& s){
int len = s.length();
int i=0, j=len-1;
while(i<j){
if(s[i]!=s[j]){
return false;
}
i++;
j--;
}
return true;
}
};
0 条评论