132. 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.
Example:
Input: "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
题意：给定一个字符串，问最少切割多少次使得每个子串都是回文
代码如下：
/** * @param {string} s * @return {number} */ var minCut = function(s) { let arr=s.split(‘‘); let n=s.length; let pal=[]; let cut=[]; for(let i=0;i<n;i++){ cut[i]=0; } for(let i=0;i<n;i++){ pal[i]=[] for(let j=0;j<n;j++){ pal[i][j]=false; } } for(let i=0;i<n;i++){ let min=i; for(let j=0;j<=i;j++){ if((arr[i]===arr[j]) && (j+1>i-1 || pal[j+1][i-1])){ pal[j][i]=true; min=j===0?0:Math.min(min,cut[j-1]+1); } } cut[i]=min; } return cut[n-1]; };
132. Palindrome Partitioning II（js）
原文：https://www.cnblogs.com/xingguozhiming/p/10928228.html