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"] ]
题目解析:
我们应该如何得到想要的结果?分析问题,要举例子找规律。比如abccbabddba。
这个里面中间的a既可以在前半区构成回文串也可以在后半区构成回文串。
那么分析各种情况:
1、每一个字符单独成串,构成一种情况。
2、下面尝试用递归的思想,a+"bccbabddba"--->a+b+"ccbabddba"....a+b...+b+"a"。
我们看a+"bccbabddba"--->a+b+ccbabddba,从下层返回到以b开始的字符串的时候,尝试让b为一个较长回文串的开始,那么一个一个找,就找到了a+bccb+"abddba",如此这样的话,就好判断了,让i从index递增,当增加到j的时候,(index,j)构成回文串,在从j+1往下面递归。
当然,这样会造成重复计算j...n的数据,可以构造一个动态规划表,[i,j]表示从i到j是否是回文串。
先看不是动态规划的算法:
class Solution { public: vector<vector<string> > partition(string s) { if(s.size() == 0) return res; vector<string> store; GeneratePartition(s,0,store); return res; } void GeneratePartition(string s,int index,vector<string> store){ if(index >= s.size()){ res.push_back(store); return ; } //找到以index为开始的所有的回文子串 for(int i = index;i < s.size();i++){ bool flag = JudgePalindrome(s,index,i); if(flag){ string tmp; for(int j = index;j <= i;j++) tmp += s[j]; store.push_back(tmp); GeneratePartition(s,i+1,store); store.pop_back(); } } } //判断是否是回文子串 bool JudgePalindrome(string s,int begin,int end){ for(int i = begin,j = end;i < j;i++,j--){ if(s[i] != s[j]) return false; } return true; } private: vector<vector<string> > res; };
用动态规划优化:
class Solution { vector<vector<string>> retVString; bool palin[1500][1500]; public: vector<vector<string>> partition(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function if(s.size() == 0) return vector<vector<string>>(); int leng = s.size(); for(int i = 0; i < leng; i++) for(int j = 0; j < leng; j++) palin[i][j] = false; //动态规划很巧妙,没有用到长度len,直接这样求解。这是因为我们不需要知道最长回文子串,仅判断[i,j]是否是回文即可 for(int i = leng-1; i >= 0; i--){ for(int j = i; j < leng; j++){ if(s[i] == s[j] && (j-i<2 || palin[i+1][j-1])){ palin[i][j] = true; } } } retVString.clear(); dfs(s, 0, vector<string>()); return retVString; } void dfs (string& s, int start, vector<string> palinStr) { if(start == s.size()) { retVString.push_back(palinStr); } for(int i = start; i < s.size(); i++) { if(palin[start][i]) { palinStr.push_back(s.substr(start, i - start + 1)); dfs(s, i+1, palinStr); palinStr.pop_back(); } } } };