LeetCode 131 Palindrome Partitioning
划分字符串，得到每一个子串都是回文串，输出所有的方案。
思路是，先将所有的回文子串都找出来，记录下左右端点。
然后DFS这些子串就可以了。
struct Node
{
string str;
int l;
int r;
Node(){}
Node(string str,int l,int r)
{
this->str =str;
this->l =l;
this->r =r;
}
}a[100005];
class Solution {
public:
int tag=0;
vector<string> res;
vector<vector<string>> ans;
vector<vector<string>> partition(string s) {
int l =s.length();
for(int i=1;i<=l;i++)
{
for(int j=0;j+i-1<l;j++)
{
if(judge(s.substr(j,i)))
a[tag++]=Node(s.substr(j,i),j,j+i-1);
}
}
dfs(0,l);
return ans;
}
void dfs(int start,int l)
{
if(start == l)
{
ans.push_back(res);
return;
}
for(int i=0;i<tag;i++)
{
if(a[i].l == start)
{
res.push_back(a[i].str);
dfs(a[i].r+1,l);
res.pop_back();
}
}
}
bool judge(string s)
{
int l = s.length();
for(int i=0,j=l-1;i<j;i++,j--)
{
if(s[i]!=s[j])
return false;
}
return true;
}
};
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
