首页 > 代码库 > Palindrome Partitioning II
Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab"
,
Return 1
since the palindrome partitioning ["aa","b"]
could be produced using 1 cut.
思路:求出划分回文区的最小剪枝次数。这道题使用回溯方法来求解不是超时就是超了内存,不知道有没有什么好的递归方法求解。经过网上资源的查找,这题AC的基本上使用动态规划来解答的。
1.首先定义dp[i]表示最小分个数在i到n-1之间。
2.定义IsPa[i][j]表示i到j子串是否是回文。
3.dp[i]=min{dp[i],dp[j+1]+1},IsPa[i][j]=Is{a[i+1][j-1]&&(s[i]==s[j])则IsPa[i][j]=true;
4.IsPa[i][j]初始化false。
class Solution { public: int minCut(string s) { int n=s.size(); vector<int> dp(n+1); for(int i=0;i<=n;i++) dp[i]=n-i; vector<vector<bool> > IsPa(n,vector<bool>(n,false)); for(int i=n-1;i>=0;i--) { for(int j=i;j<n;j++) { if(s[i]==s[j]&&(j-i<2 || IsPa[i+1][j-1])) { IsPa[i][j]=true; dp[i]=min(dp[i],dp[j+1]+1); } } } return dp[0]-1; } };
在此附上超时的做法,希望以后可以有些想法;
class Solution { public: bool IsPalindrome(string &s,int start,int end) { while(start<end) { if(s[start]!=s[end]) return false; start++; end--; } return true; } void DFS(string &s,int index,int depth,int &min) { if(index==s.size()) { if(min>depth-1) min=depth-1; return; } for(int i=s.size()-1;i>=index;i--) { if(IsPalindrome(s,index,i)) { DFS(s,i+1,depth+1,min); } } } int minCut(string s) { int min=INT_MAX; DFS(s,0,0,min); return min; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。