首页 > 其他 > 详细

[Leetcode] Palindrome Partitioning

时间:2014-04-11 09:05:58      阅读:389      评论:0      收藏:0      [点我收藏+]

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"]
  ]

像这样列举所有结果的只能DFS了。不过为什么我老是忘记写++low跟--high呢,都死循环了自己还不知道!

bubuko.com,布布扣
 1 class Solution {
 2 public:
 3     bool isPail(string &s) {
 4         int low = 0, high = s.length() - 1;
 5         while (low < high) {
 6             if (s[low] != s[high]) {
 7                 return false;
 8             }
 9             ++low;
10             --high;
11         }
12         return true;
13     }
14     
15     void findNext(vector<vector<string> > &res, string &s, vector<string> part, int idx) {
16         if (idx == s.length()) {
17             res.push_back(part);
18             return;
19         }
20         string substr;
21         for (int len = s.length() - idx; len > 0; --len) {
22             substr = s.substr(idx, len);
23             if (isPail(substr)) {
24                 part.push_back(substr);
25                 findNext(res, s, part, idx + len);
26                 part.pop_back();
27             }
28         }
29     }
30     
31     vector<vector<string>> partition(string s) {
32         vector<vector<string> > res;
33         vector<string> part;
34         findNext(res, s, part, 0);
35         return res;
36     }
37 };
bubuko.com,布布扣

 

[Leetcode] Palindrome Partitioning,布布扣,bubuko.com

[Leetcode] Palindrome Partitioning

原文:http://www.cnblogs.com/easonliu/p/3657733.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!