首页 > 代码库 > 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 };

方法三:采用动态规划的方法