题目
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"]
]
Subscribe to see which companies asked this question。
分析
给定一个字符串，将其分割为若干个回文子串集合。每个集合中的所有元素均为回文串，且元素连接结果为源串。
题目类似于之前遇到过的求全集或全排列，考察点均为回溯的思想。对于一个字符串，可以对这个字符串进行遍历，如果前pos个字符串本身是个回文字符，那么只需要求解后面的子字符的回文串即可，于是这个问题被分解成了一个更小的问题。这道题更像一个分治法的题，将问题规模不断缩小，当然的遍历字符串的过程中需要进行回溯。
AC代码
class Solution {
public:
vector<vector<string>> partition(string s) {
if (s.empty())
return vector<vector<string>>();
int len = s.length();
if (len == 1)
return vector<vector<string>>(1, vector<string>(1, s));
else
{
vector<vector<string>> ret;
int pos = 0;
while (pos < len)
{
if (isPalindrome(s, 0, pos))
{
if (pos == len - 1)
{
vector<string> tmp;
tmp.push_back(s.substr(0, pos+1));
ret.push_back(tmp);
}
else{
/*获取剩余子串的所有回文分隔结果*/
vector<vector<string>> subRet = partition(s.substr(pos + 1));
auto iter = subRet.begin();
while (iter != subRet.end())
{
(*iter).insert((*iter).begin(), s.substr(0, pos + 1));
ret.push_back(*iter);
++iter;
}//while
}//else
}//if
++pos;
}//while
return ret;
}
}
/*判断是否为回文串*/
bool isPalindrome(string str, int beg, int end)
{
if (beg <0 || beg > end || end >= str.length())
return false;
while (beg < end)
{
if (str[beg++] != str[end--])
return false;
}//while
return true;
}
};