首页 > 代码库 > 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.
class Solution {public: int minCut(string s) { int n = s.size(); vector<int> cut(n+1, 0); // number of cuts for the first k characters for (int i = 0; i <= n; i++) cut[i] = i-1; for (int i = 0; i < n; i++) { for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]); for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]); } return cut[n]; }};
Palindrome Partitioning II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。