131.Palindrome Partitioning
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 难度：Medium 返回 s 所有可能的分割方案。
示例:
输入: "aab"输出:[["aa","b"],["a","a","b"]]
直观解决方法：递归。 因为所有子数组都是回文，所以从第一个开始，找到一个回文后，将剩下的子串找出所有的可能性组合，最后再合并即可。 代码如下:
class Solution {public:vector<vector<string>> partition(string s) {int n=s.length(),cnt=0;vector<vector<string>> res;vector<string> ret;if (n == 1){ret.push_back(s);res.push_back(ret);return res;}vector<vector<string>> tmp;for(int i=1;i<n;i++){string fir=s.substr(0,i);if(ispalind(fir)){tmp=merge(fir,partition(s.substr(i,n-i)));res.insert(res.end(),tmp.begin(),tmp.end());}}if(ispalind(s)){ret.push_back(s);res.push_back(ret);}return res;}vector<vector<string>> merge(string a, vector<vector<string>>b){vector<vector<string>> res;for(int i=0;i<b.size();i++){vector<string>tmp;tmp.push_back(a);tmp.insert(tmp.end(),b[i].begin(),b[i].end());res.push_back(tmp);}return res;}bool ispalind(string s){int n=s.length();for(int i=0;i<n/2;i++)if(s[i]!=s[n-i-1]) return false;return true;}};
定义了一个函数来判断是否是回文，另一个函数用来将第一个子串和剩下的回文向量合并，最后判断整个字符串是否是回文。 但这样并不高效。因为运算时间比较长。 提交结果的一个比较好的示例如下：
class Solution {vector<vector<string>> res;void DFS(string& s, int begin, vector<string>& t){if(begin>=s.length())res.push_back(t);else{t.push_back("");for(int end=begin;end<s.length();end++)if(isParl(s, begin, end)){t[t.size()-1] = s.substr(begin, end-begin+1);DFS(s, end+1, t);}t.pop_back();}}bool isParl(string& s, int begin, int end){// 可以用DP存储加速while(begin<end){if(s[begin]!=s[end])return false;begin++;end--;}return true;}public:vector<vector<string>> partition(string s) {vector<string> t;DFS(s, 0, t);return res;}};
采用深度优先搜索DFS，也是递归调用完成。
Last updated 2 years ago