LeetCode 131 Palindrome Partitioning

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; } };

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zywzsx.html