Comment on page
131.Palindrome Partitioning
131.Palindrome Partitioning
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 难度：Medium 返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
直观解决方法：递归。 因为所有子数组都是回文，所以从第一个开始，找到一个回文后，将剩下的子串找出所有的可能性组合，最后再合并即可。 代码如下:
class Solution {
public:
vector<vector<string>> partition(string s) {
int n=s.length(),cnt=0;
vector<vector<string>> res;
vector<string> ret;
if (n == 1)
{
ret.push_back(s);
res.push_back(ret);
return res;
}
vector<vector<string>> tmp;
for(int i=1;i<n;i++)
{
string fir=s.substr(0,i);
if(ispalind(fir))
{
tmp=merge(fir,partition(s.substr(i,n-i)));
res.insert(res.end(),tmp.begin(),tmp.end());
}
}
if(ispalind(s))
{
ret.push_back(s);
res.push_back(ret);
}
return res;
}
vector<vector<string>> merge(string a, vector<vector<string>>b)
{
vector<vector<string>> res;
for(int i=0;i<b.size();i++)
{
vector<string>tmp;
tmp.push_back(a);
tmp.insert(tmp.end(),b[i].begin(),b[i].end());
res.push_back(tmp);
}
return res;
}
bool ispalind(string s)
{
int n=s.length();
for(int i=0;i<n/2;i++)
if(s[i]!=s[n-i-1]) return false;
return true;
}
};
定义了一个函数来判断是否是回文，另一个函数用来将第一个子串和剩下的回文向量合并，最后判断整个字符串是否是回文。
但这样并不高效。因为运算时间比较长。 提交结果的一个比较好的示例如下：
class Solution {
vector<vector<string>> res;
void DFS(string& s, int begin, vector<string>& t){
if(begin>=s.length())
res.push_back(t);
else{
t.push_back("");
for(int end=begin;end<s.length();end++)
if(isParl(s, begin, end)){
t[t.size()-1] = s.substr(begin, end-begin+1);
DFS(s, end+1, t);
}
t.pop_back();
}
}
bool isParl(string& s, int begin, int end){
// 可以用DP存储加速
while(begin<end){
if(s[begin]!=s[end])
return false;
begin++;
end--;
}
return true;
}
public:
vector<vector<string>> partition(string s) {
vector<string> t;
DFS(s, 0, t);
return res;
}
};
采用深度优先搜索DFS，也是递归调用完成。
Last modified 1yr ago