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”] ]
这道题还算好，不是那么变态 暴力DFS也可以通过
class Solution { public: string s; vector<vector<string>> partition(string s) { vector<vector<string> > result; vector<string> temp; this->s=s; generate(temp,result,0); return result; } void generate(vector<string> &temp,vector<vector<string> >& result,int start){ if(start==s.size()){ result.push_back(temp); return; } for(int i=start;i<s.size();i++){ if(palindrome(s,start,i)){ temp.push_back(s.substr(start,i-start+1)); generate(temp,result,i+1); temp.pop_back(); } } } bool palindrome(string &s,int start,int end){ while(start<end && s[start]==s[end]){ start++;end--; } return start>=end; } };II 又是一个醉到不行的题目。 可行的剖分最少的情况。 看起来比较像DP问题。 一开始想到的思路是 对于一个串 abcbm 令dp[i][j]为i~j子序列中需要的最小切割数量，那么它可以被分为如下两种情况
一是i~j本身为回文，则结果为0另一是本身不为回文，则结果为dp[i][j]=1+min(dp[i][k]+dp[k+1][j);即我们遍历整个i~j数组并看切分的组合哪一个最小+切分开的一次计数。理论上这种应当是O(n^3)这种可以优化到O(N^2) 我们从后往前推【事实上从前往后也是一样的】 当我们知道i~j是一个回文的时候，我们想知道j+1~n可以被剖分多少次。 什么意思呢， 参考地址：http://www.allenlipeng47.com/blog/index.php/2016/07/23/palindrome-partitioning-ii/ 使用一个一位数组p[i]存放0~i【以i位置结尾】的时候，即对于i长度的串最少需要切几次。
例如这个图【不过它是从前往后推的，dp方程变成p[j]=min(p[j],p[i-1]+1】
也就是确认了i~j是回文串之后，需要知道这个回文串之前的【i-1结尾的】需要切几次。再加上这一次的切割。 于是可以得出DP方程并写出程序…
十分蛋疼的是int[][] 爆内存了，以后这种标记数组还是直接用一个char好了
class Solution { public: int minCut(string s) { int n=s.size(); int p[n]; char dp[n][n]; memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) dp[i][i]=1; for(int i=0;i<n;i++) p[i]=n-1-i; for(int i=n-1;i>=0;i--){ for(int j=i;j<n;j++){ if(s[i]==s[j]){ if(j==i+1 || j==i) dp[i][j]=1; else dp[i][j]=dp[i+1][j-1]; } if(dp[i][j]){ if(j==n-1) p[i]=0; p[i]=min(p[i],p[j+1]+1); } } } return p[0]; } }