好贷网好贷款

Palindrome Partitioning

发布时间:2016-12-4 5:58:58 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Palindrome Partitioning",主要涉及到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"] ] 首先此题跟组合(Subsets),Restore IP Addresses很像,都可以用深搜的方法! 个人错误小结:(刚开始报limit,以为是深搜办法不行,后面发现大家都行,后面终于找到错误!) partition_dfs(s,i+1,ans,result);//之前由于笔误写成index+1(死循环!),一直报limit错误 vector<vector<string>> partition(string s) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. vector<string> ans; vector<vector<string>> result; partition_dfs(s,0,ans,result); return result; } void partition_dfs(string s,int index,vector<string> ans,vector<vector<string>> &result) { if(s.size() == index) { result.push_back(ans); return ; } else { string str ; for(int i = index; i < s.size(); i++) { str = s.substr(index,i-index+1); if(is_palindrome(str)) { ans.push_back(str);//提取相应的段 partition_dfs(s,i+1,ans,result);//之前由于笔误写成index+1(死循环!),一直报limit错误 ans.pop_back(); } } } } bool is_palindrome(string s) { int start = 0; int end = s.size()-1; while(start < end) { if(s[start] != s[end])return false; start++; end--; } return true; }

上一篇:压缩和解压缩
下一篇:【题解】[scoi2005]繁忙的都市

相关文章

相关评论