首页 > 代码库 > [LeetCode] Palindrome Partitioning
[LeetCode] 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 private: 3 vector<vector<string> > m_res; 4 public: 5 vector<vector<string> > partition(string s) 6 { 7 size_t size = s.size(); 8 if(size == 0) 9 return m_res;10 11 vector<string> str;12 dfs(s, 0, size - 1, str);13 return m_res;14 }15 16 void dfs(string s, size_t begin, size_t end, vector<string>& str)17 {18 if(begin > end)19 {20 m_res.push_back(str);21 return;22 }23 24 for(size_t i = begin; i<= end; i++)25 {26 if(isPalindrome(s, begin, i))27 {28 str.push_back(s.substr(begin, i-begin + 1));29 dfs(s, i+1, end, str);30 str.pop_back();31 }32 }33 }34 35 bool isPalindrome(string s, size_t begin, size_t end)36 {37 if(begin == end)38 return true;39 while(begin <= end)40 {41 if(s[begin] == s[end])42 {43 begin++;44 end --;45 }46 else47 return false;48 }49 return true;50 }51 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。