131.Palindrome Partitioning
131.Palindrome Partitioning
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 难度:Medium 返回 s 所有可能的分割方案。
示例:
1
输入: "aab"
2
输出:
3
[
4
["aa","b"],
5
["a","a","b"]
6
]
Copied!
直观解决方法:递归。 因为所有子数组都是回文,所以从第一个开始,找到一个回文后,将剩下的子串找出所有的可能性组合,最后再合并即可。 代码如下:
1
class Solution {
2
public:
3
vector<vector<string>> partition(string s) {
4
int n=s.length(),cnt=0;
5
vector<vector<string>> res;
6
vector<string> ret;
7
if (n == 1)
8
{
9
ret.push_back(s);
10
res.push_back(ret);
11
return res;
12
}
13
14
vector<vector<string>> tmp;
15
for(int i=1;i<n;i++)
16
{
17
string fir=s.substr(0,i);
18
if(ispalind(fir))
19
{
20
tmp=merge(fir,partition(s.substr(i,n-i)));
21
res.insert(res.end(),tmp.begin(),tmp.end());
22
}
23
}
24
if(ispalind(s))
25
{
26
ret.push_back(s);
27
res.push_back(ret);
28
}
29
return res;
30
31
}
32
vector<vector<string>> merge(string a, vector<vector<string>>b)
33
{
34
vector<vector<string>> res;
35
36
for(int i=0;i<b.size();i++)
37
{
38
vector<string>tmp;
39
tmp.push_back(a);
40
tmp.insert(tmp.end(),b[i].begin(),b[i].end());
41
res.push_back(tmp);
42
}
43
return res;
44
}
45
bool ispalind(string s)
46
{
47
int n=s.length();
48
for(int i=0;i<n/2;i++)
49
if(s[i]!=s[n-i-1]) return false;
50
return true;
51
}
52
};
Copied!
定义了一个函数来判断是否是回文,另一个函数用来将第一个子串和剩下的回文向量合并,最后判断整个字符串是否是回文。 但这样并不高效。因为运算时间比较长。 提交结果的一个比较好的示例如下:
1
class Solution {
2
vector<vector<string>> res;
3
4
void DFS(string& s, int begin, vector<string>& t){
5
if(begin>=s.length())
6
res.push_back(t);
7
else{
8
t.push_back("");
9
for(int end=begin;end<s.length();end++)
10
if(isParl(s, begin, end)){
11
t[t.size()-1] = s.substr(begin, end-begin+1);
12
DFS(s, end+1, t);
13
}
14
t.pop_back();
15
}
16
}
17
18
19
bool isParl(string& s, int begin, int end){
20
// 可以用DP存储加速
21
while(begin<end){
22
if(s[begin]!=s[end])
23
return false;
24
begin++;
25
end--;
26
}
27
return true;
28
}
29
public:
30
vector<vector<string>> partition(string s) {
31
vector<string> t;
32
DFS(s, 0, t);
33
return res;
34
}
35
};
Copied!
采用深度优先搜索DFS,也是递归调用完成。
Copy link