problem:
Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return all possible palindrome partitioning ofs.
For example, givens="aab",Return
[["aa","b"],["a","a","b"] ]
Hide Tags
Backtracking
题意:检查字符串的所有子字符串是否为回文字符串
thinking:
(1)这道题理论上不难,采用回溯法遍历所有的子字符串,再检查子字符串是否为回文字符串即可
(2)但难点在于,,输出格式得满足判定程序。这一点我的输出格式没能通过。如:
Input:"ab"Output:[["a"],["b"]]Expected:[["a","b"]]
有 时间再研究怎么改吧
code:
class Solution {private: vector<vector<string> > ret; vector<string> tmp;public:vector<vector<string>> partition(string s) {ret.clear();tmp.clear();if(s.size()==0)return ret;check(s,0,0);return ret;}protected: void check(string s,int start, int end){if(start>s.size()-1)return;string str=s.substr(start,end-start+1);if(ispalindrome(str))tmp.push_back(str);if(end<s.size()-1)check(s,start,end+1);if(end==s.size()-1){if(tmp.size()!=0)ret.push_back(tmp);tmp.clear();check(s,start+1,start+1);}} bool ispalindrome(string s){int n=s.size();int i=0;int j=n-1;while(i<=j){if(s.at(i)==s.at(j)){i++;j–;}elsereturn false;}return true;}};
坚守自己的原则,世界上的诱-惑很多,