首页 > 代码库 > [LeetCode] Palindrome Partition [11]
[LeetCode] Palindrome Partition [11]
题目
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"] ]
原题链接
解题思路
回文划分,题目意思是给一个字符串,找出将字符串划分为一系列回文子串的各种可能组合。例如,一个子串“aab“,你需要返回["aa","b"],["a","a","b"]。这个题目的解法也是非常的典型---循环加递归,这是解决组合排列问题的标准解法。Leetcode上面还有许多这种解法的题目。
对于aab:
判断a,再判断ab;
ab:先判断a,在判断b;
b:判断完,结束
判断aa,再判断b
b:判断完,结束
其余的看代码理解吧。
代码实现
class Solution { public: vector<vector<string> > partition(string s) { vector<vector<string> > ret; vector<string> part; helper(0, s, part, ret); return ret; } void helper(int start, const string &s, vector<string> part, vector<vector<string> > &ret){ int n = s.size(); if(start == n){ ret.push_back(part); return ; } for(int i=start; i<n; ++i){ string temp = s.substr(start, i-start+1); if( !validPalindrome(temp)) continue; part.push_back(temp); helper(i+1, s, part, ret); part.pop_back(); } } bool validPalindrome(string s){ int begin = 0, end = s.size()-1; while(begin<end){ if(s[begin] != s[end]) return false; ++begin, --end; } return true; } };
如果你觉得本篇对你有收获,请帮顶。
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你可以搜索公众号:swalge 或者扫描下方二维码关注我
(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/28889301 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。