题目：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"]]

思路：

这道题目使用回溯法，当然不可少的就是回文串的判断，另外写一个程序判断即可。

另外一个就是当start到达s的长度的时间，就返回。在每一个程序里面，start代表从start位置到最后一个位置的所有可能性。循环里面i从start到s的长度大小进行循环。循环里面判断从start到i是否是回文串，是的话然后push进去，当然最终是要pop出来的。继续把下一个start设置为i+1。

代码：

class Solution { public: //https://leetcode.com/problems/palindrome-partitioning/vector<vector<string>> partition(string s) {vector<string> tmp;vector< vector<string> > result;int length=s.length();if(length==0){return result;}partitionHelper(0,s,tmp,result);return result;}void partitionHelper(int start,string &s,vector<string> &tmp,vector< vector<string> > &result){if(start==s.length()){result.push_back(tmp);return;}for(int i=start;i<s.length();i++){if(isPalindrome(start,i,s)){tmp.push_back(s.substr(start, i-start+1) );//左闭右开partitionHelper(i+1,s,tmp,result);tmp.pop_back();}}}bool isPalindrome(int start,int end,string &s){int mid=(start+end)/2;int i=start,j=end;while(i<=j){if(s[i++]!=s[j--]){return false;}}return true;} };

转载于:https://www.cnblogs.com/jsrgfjz/p/8519880.html

总结

以上是生活随笔为你收集整理的Palindrome Partitioning的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。