🤖 leetcode 132. Palindrome Partitioning II | hard | dynamic-programming | javascript

🗒️ Problems

132. Palindrome Partitioning II - Leetcode

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.

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

Constraints:

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

🤔 Understand problem

• Split given string into palindrome substring.
• Find minimum number of cuts (splits).

🤦‍♂️ First attempt

• Backtracking is my favorite, but it causes TLE.

var minCut = function (s) {
  let min = Infinity;
  const cache = {};

  const isP = (str) => {
    if (cache[str] !== undefined) return cache[str];

    let res = true;
    let left = 0;
    let right = str.length - 1;
    while (left < right) {
      if (str[left] !== str[right]) {
        res = false;
        break;
      }
      left += 1;
      right -= 1;
    }
    return (cache[str] = res);
  };

  const dfs = (cur, remain) => {
    if (remain.length === 0) {
      if (min > cur.length - 1) min = cur.length - 1;
      return;
    }

    for (let i = 0; i < remain.length; i += 1) {
      const sub = remain.slice(0, i + 1).join("");
      if (!isP(sub)) continue;

      cur.push(sub);
      dfs(cur, remain.slice(i + 1));
      cur.pop();
    }
  };

  dfs([], s.split(""));

  return min;
};

🙅‍♂️ Failed time complexity : O(N 2^N)

• Input can be upto 2000.
• O(2^N) backtracking won't work.

🥳 Think differently

• We have to reuse the redundant call in a recursive call.
• Can we use top-down dynamic programming ?

✨ Idea

• If we split into one character, there are N-1 cuts, which is the maximum.

  0      ...      N-1
start             end  => max cuts = N -1

• Let's find smaller cuts using top-down approach.

dp(start, end, cuts);
// answer will be dp(0, N-1, N-1)

🍀⬇️ palindrome check using start and end

• top-down palindrome check function

const isPalindrome = (start, end) => {
  if (start >= end) return true;

  return s[start] === s[end] && isPalindrome(start + 1, end - 1);
};

💡⬇️ Top down dp() function

dp(start, end, cuts) returns how many minimum cuts are there in s[start:end].

basecase

• If start and end are same, we can't cut more, so that its cut is 0.
• If this word is palindrome itself, we can't cut more, so that its cut is 0.

const dp = (start, end, count) => {
 if (start === end || isPalindrome(start, end)) return 0
    ...
}

dp(start, end, cuts) main code

• It's challenging to derive this function.

const dp = (start, end, count) => {
  // basecase

  for (let i = start; i <= end; i += 1) {
    if (isPalindrome(start, i)) {
      count = Math.min(count, 1 + dp(i + 1, end, count));
    }
  }
  return count;
};

⬇️ top-down without memoization.

• It works, but TLE occurs.

var minCut = function (s) {
  const N = s.length;

  const isPalindrome = (start, end) => {
    if (start >= end) return true;

    return s[start] === s[end] && isPalindrome(start + 1, end - 1);
  };

  const dp = (start, end, count) => {
    if (start === end || isPalindrome(start, end)) return 0;

    for (let i = start; i <= end; i += 1) {
      if (isPalindrome(start, i)) {
        count = Math.min(count, 1 + dp(i + 1, end, count));
      }
    }
    return count;
  };

  return dp(0, N - 1, N - 1);
};

💡⬇️ Add momoization

• dpCuts[start][end] : minimum cuts between start and end
• dpPalindrome[start][end] : is palindrome between start and end

const dpCuts = Array(N)
  .fill(null)
  .map((_) => Array(N));
const dpPalindrome = Array(N)
  .fill(null)
  .map((_) => Array(N));

🔥⬇️ My Solution

/**
 * @param {string} s
 * @return {number}
 */
var minCut = function (s) {
  const N = s.length;

  const dpCuts = Array(N)
    .fill(null)
    .map((_) => Array(N));
  const dpPalindrome = Array(N)
    .fill(null)
    .map((_) => Array(N));

  const isPalindrome = (start, end) => {
    if (start >= end) return true;
    if (dpPalindrome[start][end] !== undefined) return dpPalindrome[start][end];

    return (dpPalindrome[start][end] =
      s[start] === s[end] && isPalindrome(start + 1, end - 1));
  };

  const dp = (start, end, count) => {
    if (start === end || isPalindrome(start, end)) return 0;
    if (dpCuts[start][end] !== undefined) return dpCuts[start][end];

    for (let i = start; i <= end; i += 1) {
      if (isPalindrome(start, i)) {
        count = Math.min(count, 1 + dp(i + 1, end, count));
      }
    }
    return (dpCuts[start][end] = count);
  };

  return dp(0, N - 1, N - 1);
};

🙆‍♂️ Time complexity: O(n)