鏈接：https://www.nowcoder.com/PRactice/1025ffc2939547e39e8a38a955de1dd3?tpId=46&tqId=29048&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking 來源：牛客網
題目描述
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”, Return1since the palindrome partitioning[“aa”,”b”]could be produced using 1 cut.
class Solution { int dp[1000]={0}; int hw[1000][1000]={0};public: int minCut(string s) { int i,k,N=s.length(); if(s.length()==0) return 0; hwb(s); for(i=0;i<s.length();i++) { if(hw[0][i]==1) dp[i]=0; else { dp[i]=9999; for(k=i;k>0;k--) if(hw[k][i]==1) dp[i]=min(dp[i],dp[k-1]+1); } } return dp[N-1]; } void hwb(string s) { int i,j; for(i=s.length()-1;i>=0;i--) for(j=i;j<s.length();j++) { if(i==j) hw[i][j]=1; else if(j-i==1) { if(s[i]==s[j]) hw[i][j]=1; } else { if(s[i]==s[j]&&hw[i+1][j-1]==1) hw[i][j]=1; } } }};新聞熱點
疑難解答
