首页 > 代码库 > 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"] ]
与Restore IP Addresses类似。。都使用回溯法。。。
C++实现代码：
#include<iostream>#include<vector>#include<string>using namespace std;class Solution{public: vector<vector<string>> partition(string s) { if(s.empty()) return vector<vector<string> >(); vector<vector<string> > ret; vector<string> path; helper(s,0,ret,path); return ret; } void helper(string s,int start,vector<vector<string> > &ret,vector<string> &path) { int n=path.size(); int i; int sum=0; for(int j=0; j<n; j++) { sum+=path[j].size(); } if(sum==(int)s.size()) { ret.push_back(path); return; }
//start+i<=(int)s.size()是为了分割的最后一个字符串不重复。 for(i=1; i<=(int)s.size()&&start+i<=(int)s.size(); i++) { string tmp=s.substr(start,i); if(!isPalindrome(tmp)) continue; path.push_back(tmp); helper(s,start+i,ret,path); path.pop_back(); } } bool isPalindrome(string s) { if(s.empty()) return true; int i=0; int j=s.length()-1; while(i<=j) { if(s[i]!=s[j]) return false; i++; j--; } if(i>j) return true; return false; }};int main(){ Solution s; vector<vector<string> > result=s.partition(string("aab")); for(auto a:result) { for(auto v:a) cout<<v<<" "; cout<<endl; }}
运行结果：
Palindrome Partitioning
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。