首页 > 代码库 > leetcode第一刷_ Palindrome Partitioning II
leetcode第一刷_ Palindrome Partitioning II
这道题还挺复杂的,回来看了好一会儿才想起当时怎么想的。。上道题刚说不要打表,这道题就用了打表。。
总的思路是这样的,从后面往前面打表,最后一个位置的最小分割一定是0,那往前呢,如果当前考虑的位置是start,并且substr(s, i)是回文的,那么如果已知i+1开始的分割次数,那么start这个位置的分割应该就是start原来的和i+1开始的分割次数加1之间的最小值。DP的思想,很直接。
但是我忽略了一个另一个开销很大的地方,那就是每次判断回文的时候。这个跟单词分割还不一样,这个范围很大。最后居然开了个很大的二维数组,记录每个位置的起始结束是不是回文,直接打脸了。。建这个表的时候,我先把两头的回文计算了一遍,当计算中间部分的时候,直接用这两头的结果。其实想法很简单,如果i+1和j-1之间是不是回文已经知道了,那么i和j就不用从头算了,看看i和j位置相不相等,按照情况更新就行了。
这道题应该有更优雅的算法,回头找到了贴上来,先贴我的。
int MAX = 0xfffffff; bool isp[2000][2000]; bool isPalindrome(string &s, int start, int end){ for(int i=start, j=end;i<j;++i, --j){ if(s[i] != s[j]) return false; } return true; } void getPartition(string &s, int start, vector<int> &minpartition){ if(start == s.length()){ minpartition[start] = 0; return; } for(int i=start;i<s.length();++i){ if(isp[start][i]){ if(minpartition[i+1] == MAX) getPartition(s, i+1, minpartition); minpartition[start] = min(minpartition[start],minpartition[i+1]+1); } } } class Solution { public: int minCut(string s) { if(s.length()<=1) return 0; int len = s.length(); memset(isp, 0, sizeof(isp)); for(int i=0;i<len;i++){ isp[0][i] = isPalindrome(s, 0, i); } for(int i=1;i<len;i++){ isp[i][len-1] = isPalindrome(s, i, len-1); } for(int i=len-2;i>0;i--){ for(int j=i;j<len-1;j++){ if(i == j) isp[i][j] = 1; else if(j == i+1) isp[i][j] = s[i]==s[j]; else isp[i][j] = isp[i+1][j-1]&&s[i]==s[j]; } } vector<int> minpartition(len+1, MAX); getPartition(s, 0, minpartition); return minpartition[0]-1; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。