首页 > 代码库 > 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"]  ]    
分析:用dfs暴力搜索。
 1 class Solution { 2 public: 3     vector<vector<string>> partition(string s) { 4         vector<vector<string>> res; 5         if(s.length() == 0) return res; 6         vector<string> path; 7         dfs(res,path,s,0); 8     } 9     void dfs(vector<vector<string>> & res, vector<string> & path, string s, int start){10         if(start == s.length()) res.push_back(path);11         for(int i = start; i < s.length(); i++){12             if(isPalindrome(s,start,i)){13                 path.push_back(s.substr(start,i-start+1));14                 dfs(res,path,s,i+1);15                 path.pop_back();16             }17         }18     }19     bool isPalindrome(string s, int start, int end){20         if(start == end) return true;21         int i = start, j = end;22         for(; i <= (start + end)/2 && s[i] == s[j]; i++, j--);23         if(i > (start+end)/2) return true;24         return false;25     }26 };