首页 > 代码库 > 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.
分析：这道题可以用动态规划来解。这里介绍两种实现方法，一种是用一个二维bool数组word[i][j]记录s[i,j]是否为palindrome用一个一维int数组f[i]记录s[0,i]的最少cut数。
另一种方法是只用一个二维数组f[i][j]记录s[i,j]最小cut数，因为如果s[i,j]是palindrome那么s[i][j] = 0，所以s[i][j]同时可以用来记录s[i,j]是否为palindrome。
方法一实现：
class Solution {public: int minCut(string s) { vector<int> f(s.length()+1,0); vector<vector<bool>> words(s.length()+1, vector<bool>(s.length()+1,false)); for(int i = 0; i < s.length()+1; i++) f[i] = i-1; for(int i = 0; i < s.length()+1; i++) words[i][i] = true; for(int i = 1; i < s.length() + 1; i++){ for(int j = i-1; j >= 0; j--){ if(s[j] == s[i-1] && (i-j <= 2 || words[j+1][i-2])){ words[j][i-1] = true; f[i] = min(f[j]+1,f[i]); } } } return f[s.length()]; }};
方法二实现：
class Solution {public: int minCut(string s) { int n = s.length(); if(n == 0 || n == 1) return 0; vector<vector<int> > f(n, vector<int>(n, INT_MAX)); for(int i = n-1; i >=0; i--) for(int j = i; j < n; j++){ if(i == j || s[i] == s[j] && (i == j-1 || f[i+1][j-1] == 0)){ f[i][j] = 0; if(j < n-1)f[i][n-1] = min(f[i][n-1], f[j+1][n-1]+1); } } return f[0][n-1]; }};
Leetcode:Palindrome Partitioning II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。