132. Palindrome Partitioning II

Description

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 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters only.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const minCut = function (s) {
  const n = s.length;
  const cuts = new Array(n).fill(0);
  const isPalindrome = new Array(n)
    .fill('')
    .map(_ => new Array(n).fill(false));

  for (let a = 0; a < n; a++) {
    cuts[a] = a;

    for (let b = 0; b <= a; b++) {
      if (s[a] !== s[b]) continue;
      if (a - b > 1 && !isPalindrome[a - 1][b + 1]) continue;
      isPalindrome[a][b] = true;
      cuts[a] = b ? Math.min(cuts[a], cuts[b - 1] + 1) : 0;
    }
  }
  return cuts[n - 1];
};