Leetcode Index

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,也是递归调用完成。