1745. Palindrome Partitioning IV

Description

Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false.​​​​​

A string is said to be palindrome if it the same string when reversed.

 

Example 1:

Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.

Example 2:

Input: s = "bcbddxy"
Output: false
Explanation: s cannot be split into 3 palindromes.

 

Constraints:

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

 

Solutions

Solution: Dynamic Programming

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

 

JavaScript

/**
 * @param {string} s
 * @return {boolean}
 */
const checkPartitioning = function (s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(null));

  const isPalindrome = (a, b) => {
    if (a >= b) return true;
    if (dp[a][b] !== null) return dp[a][b];
    const result = s[a] === s[b] && isPalindrome(a + 1, b - 1);

    dp[a][b] = result;

    return result;
  };

  for (let a = 0; a < n - 2; a++) {
    const segment1 = isPalindrome(0, a);

    if (!segment1) continue;

    for (let b = a + 1; b < n - 1; b++) {
      const segment2 = isPalindrome(a + 1, b);

      if (!segment2) continue;
      const segment3 = isPalindrome(b + 1, n - 1);

      if (segment3) return true;
    }
  }

  return false;
};