原题
LintCode 136. Palindrome Partitioning
Description
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example
Given s = "aab", return:
[
["aa","b"],
["a","a","b"]
]
解题
题意为给定一个字符串，将其分割为每个字串都是回文字符串。给出所有的分割方法。
使用递归的方式，每个字符串都可以将前n个字符组成一个回文子串，剩下的字符继续传入递归。
代码
class Solution {
public:
/*
* @param s: A string
* @return: A list of lists of string
*/
vector<vector<string>> partition(string &s) {
// write your code here
helper(s);
return ans;
}
private:
vector<vector<string>> ans;
vector<string> cur;
void helper(string str) {
if (str.length()) {
for (int i = 0; i < str.length(); i++) {
string sub = str.substr(0, i + 1);
if (check(sub)) {
cur.push_back(sub);
helper(str.substr(i + 1));
cur.pop_back();
}
}
} else {
ans.push_back(cur);
}
}
bool check(string &str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
if (str[i] != str[j]) return false;
}
return true;
}
};
