首页 > 代码库 > 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 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。