首页 > 代码库 > leetcode之Palindrome Partitioning
leetcode之Palindrome Partitioning
方法一:DFS递归,判断每一个是否为回文数
1,首先要有一个判断字符串是否是回文的函数。容易实现,字符串从两边同时往中间走,看字符是否相同; 2,深度优先搜索思想对字符串进行遍历。得到结果。例如,s = "abacd"; 需要对“a”“ad”“aba”“abac”“abacd”进行深度优先搜索。深度搜索的过程如下:先选“a”,发现“a”是回文,则深度遍历“bacd”,继续深度遍历,“b”也是回文,深度遍历“acd”,继续下去; 同时,深度遍历“a”的同时,也需要深度遍历“ab”,“aba”,“abac”,“abacd”。发现只有“aba”是回文,所以继续深度搜索“cd”。
1 class Solution { 2 public: 3 vector<vector<string>> result; 4 void DFS(string str, vector<string>& curSubStrs, int start, int end) 5 { 6 if(start>end) 7 { 8 result.push_back(curSubStrs); 9 return; 10 } 11 for(int k=start;k<=end;k++) 12 { 13 string r=str.substr(start,k-start+1); 14 if(palindrom(r)) 15 { 16 curSubStrs.push_back(r); 17 DFS(str,curSubStrs,k+1,end); 18 curSubStrs.pop_back(); 19 } 20 } 21 } 22 bool palindrom(string r) 23 { 24 int n=r.size()-1; 25 int s=0; 26 while(s<n) 27 { 28 if(r[s]!=r[n]) 29 return false; 30 s++; 31 n--; 32 } 33 return true; 34 } 35 vector<vector<string>> partition(string s) { 36 int n=s.size(); 37 result.clear(); 38 if(n<0) return result; 39 vector<string> tmp; 40 DFS(s,tmp,0,n-1); 41 return result; 42 } 43 };
方法二:也是递归,只不过是换个方式的方法
1 //方法二,同样递归,但是只是处理小技巧上方法,其实第一次是想这么做得 2 class Solution { 3 public: 4 vector<vector<string>> res; 5 vector<vector<string>> partition(string s) { 6 int n=s.size(); 7 vector<string> tmp; 8 dfs(s,tmp); 9 return res; 10 } 11 bool palindrom(string r) 12 { 13 int n=r.size()-1; 14 int s=0; 15 while(s<n) 16 { 17 if(r[s]!=r[n]) 18 return false; 19 s++; 20 n--; 21 } 22 return true; 23 } 24 void dfs(string s,vector<string>&tmp) 25 { 26 if(s.size()<1) //s是空串 27 { 28 res.push_back(tmp); 29 return; 30 } 31 for(int i=0;i<s.size();i++) 32 { 33 string st=s.substr(0,i+1); //i+1是长度,从0开始,长度是i+1,其实主要是递归的思想,小的递归和大的递归实际是一样的,所以做题时可以根据最大的递归来想最小的递归是否正确 34 if(palindrom(st)) 35 { 36 tmp.push_back(st); 37 dfs(s.substr(i+1),tmp); //没有第一个参数时就是从i+1到组后 38 tmp.pop_back(); 39 } 40 41 } 42 } 43 }; 方法三:采用动态规划的方法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。