Palindrome Partitioning

发布时间:2014-10-22 19:41:33
来源:分享查询网

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

返回顶部
查看电脑版