好贷网好贷款

leetcode解析回文子串拆分

发布时间:2016-12-5 22:33:17 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"leetcode解析回文子串拆分",主要涉及到leetcode解析回文子串拆分方面的内容,对于leetcode解析回文子串拆分感兴趣的同学可以参考一下。

转载请注明来自souldak,微博:@evagle 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"] ] 思路: 假设长度为1,2...i的拆分已经都知道了,用C[i]表示,现在考虑s[i+1], 1. s[i+1]自己分为一组,C[i+1]中加入C[i]中每一种拆分加上s[i+1]的结果 2. s[i+1]与前k个构成回文,即s[i+1]s[i]...s[i-k+1]是回文,那么C[i+1]加入C[k]中的每种拆分加上s[i+1]s[i]...s[i-k+1]的结果 最终就得到了C[i+1] 举个例子:aab,现在C[0]={{a}} 现在看C[1].分两种情况,s[1]单独一个字符串{a,a},s[1]和s[0]构成回文{aa}。 C[1]={{a,a},{aa}} C[2]类似,b自己单独,那就是C[1]中的每个集合加入b,得到{{a,a,b},{aa,b}} 再检测b与前k个字符是否构成回文,发现不能构成回文了,所以最终结果就是{{a,a,b},{aa,b}} CODE: /** * @file Palindrome_Partitioning.cpp * @Brief * @author Brian * @version 1.0 * @date 2013-09-06 */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <memory.h> #include <algorithm> #include <math.h> #include <queue> #include <vector> using namespace std; #define MAXINT 0x7fffffff class Solution { public: struct Node{ vector< vector<string> > vstr ; }; vector<vector<string> > partition(string s) { int len = s.length(); Node* nodes = new Node[len]; vector<string> str0; str0.push_back(s.substr(0,1)); nodes[0].vstr.push_back(str0); for(int i=1;i<len;i++){ for(int j=0;j<=i;j++){ string subs = s.substr(j,i-j+1); if(is_palindrome(subs)){ if(j==0){ vector<string> tmp; tmp.push_back(subs); nodes[i].vstr.push_back(tmp); }else{ for(int k=0;k<nodes[j-1].vstr.size();k++){ vector<string> tmp; vector<string> pre = nodes[j-1].vstr[k]; for(int p=0;p<pre.size();p++){ tmp.push_back(pre[p]); } tmp.push_back(s.substr(j,i-j+1)); nodes[i].vstr.push_back(tmp); } } } } } return nodes[len-1].vstr; } bool is_palindrome(string s){ if(s.length() <= 1) return true; else{ for(int i=0;i<s.length()/2;i++){ if(s[i]!=s[s.length()-i-1]){ return false; } } } return true; } void printv (vector<vector<string> > str){ for(int i=0;i<str.size();i++){ for(int j=0;j<str[i].size(); j++){ cout<<str[i][j]<<"\t"; } cout<<endl; } } }; int main(){ Solution s; s.printv(s.partition("a")); return 0; }

上一篇:vijos P1097 合并果子
下一篇:Code Fragment-通过位运算来表达状态

相关文章

相关评论