首页 > 代码库 > leetcode -- Palindrome Partitioning II
leetcode -- 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.
[解题思路]
ans[i]表示s[i]至最后需要的划分数
注意:line6 "<="
1 int Solution::minCut(string s){ 2 const int len = s.length(); 3 bool pali[len][len]; 4 int ans[len]; 5 fill_n(&pali[0][0], len*len, false); 6 for (int i = 0; i <= len; i++) 7 ans[i] = len - i - 1; 8 for (int i = len - 1; i >= 0; i --){ 9 for (int j = i; j < len; j ++){10 pali[i][j] = s[i]==s[j]&&(j-i<2||pali[i+1][j-1]);11 pali[i][j] == true?(ans[i] = min(ans[i], ans[j + 1] + 1)):(true);12 }13 }14 return ans[0];15 }
leetcode -- Palindrome Partitioning II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。