首页 > 代码库 > [leetcode] Palindrome Partitioning
[leetcode] Palindrome Partitioning
Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[ ["aa","b"], ["a","a","b"] ]
思路：
还是dfs的题目。将字符串分割成两个小字符串是s1和s2，要保证s1一定要是回文的，然后继续对s2进行分割，这就是递归了。字符串分隔成s1和s2的时候，s1的长度有小到大，逐一判断s1是不是回文字符串。这样在分割s2的时候就不用考虑s1有没有更小的分割情况，因为更小的已经提前考虑了。递归越来越深，如果最终的分割使字符串为空，说明之前的所有分割都找到了一个回文字符串了，这就是一种可行解。
题解：
class Solution {public: vector<vector<string> > res; vector<string> tmp; bool isPalin(string s) { int i,j; for(i=0,j=s.size()-1;i<j;i++,j--) if(s[i]!=s[j]) return false; return true; } void dfs(string s) { if(s.empty()) { res.push_back(tmp); return; } for(int i=0;i<s.size();i++) { string s1 = s.substr(0,i+1); if(isPalin(s1)) { tmp.push_back(s1); dfs(s.substr(i+1)); tmp.pop_back(); } } } vector<vector<string>> partition(string s) { /*if(s.empty()) return res;*/ dfs(s); return res; }};
后话：
再给出一个方法，时间复杂度更低的。
[leetcode] Palindrome Partitioning
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。