[LeetCode]131.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”] ]

思路

此题可以用回溯法解决。把字符串s分为前后两个字串 str1, str2；如果str1是回文，加入partition，然后递归str2.

代码

/**————————————* 日期：2015-03-02* 作者：SJF0115* 题目: 131.Palindrome Partitioning* 网址：https://oj.leetcode.com/problems/palindrome-partitioning/* 结果：AC* 来源：LeetCode* 博客：—————————————**/;class Solution {public:vector<vector<string> > partition(string s) {vector<string> path;vector<vector<string> > result;int size = s.size();if(size <= 0){return result;}//ifPartition(s,size,0,path,result);return result;}private:Partition(string str,int size,int start,vector<string> &path,vector<vector<string> > &result){// 终止条件if(start == size){result.push_back(path);return;}//ifstring substr;// 分割字符串for(int i = start;i < size;++i){substr = str.substr(start,i-start+1);// 判断是否是回文串if(IsPalindrome(substr)){path.push_back(substr);Partition(str,size,i+1,path,result);path.pop_back();}//if}//for}// 判断字符串是否是回文串bool IsPalindrome(string str){int size = str.size();if(size == 0){return false;}//ifint left = 0;int right = size – 1;while(left < right) {if(str[left] != str[right]) {return false;}//ifleft++;right–;};}};int main(){Solution s;string str(“aaba”);vector<vector<string> > result = s.partition(str);// 输出for(int i = 0;i < result.size();++i){for(int j = 0;j < result[i].size();++j){cout<<result[i][j]<<” “;}//forcout<<endl;};}

运行时间

，我们大都接受的是正面的教育，