132

132. Palindrome Partitioning II (Hard)

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.

Companies: Amazon, Apple, Bloomberg, Yahoo, TikTok

Related Topics:
String, Dynamic Programming

Similar Questions:

• Palindrome Partitioning (Medium)
• Palindrome Partitioning IV (Hard)
• Maximum Number of Non-overlapping Palindrome Substrings (Hard)
• Number of Great Partitions (Hard)

Solution 1.

Let dp[i+1] be the minimum number of palindrome segments partitioned from s[0..i].

dp[0] = 0
dp[i+1] = min( dp[j] + 1 | p[j][i] is true )

The answer is dp[N]

// OJ: https://leetcode.com/problems/palindrome-partitioning-ii
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    int minCut(string s) {
        bool p[2000][2000] = {}; // p[i][j] = true if s[i][j] is a palindrome
        int N = s.size(), dp[2001] = {};
        for (int i = 0; i < N; ++i) {
            p[i][i] = true;
            for (int k = 1; i - k >= 0 && i + k < N && s[i - k] == s[i + k]; ++k) p[i - k][i + k] = true;
            if (i - 1 >= 0 && s[i - 1] == s[i]) {
                p[i - 1][i] = true;
                for (int k = 1; i - 1 - k >= 0 && i + k < N && s[i - 1 - k] == s[i + k]; ++k) p[i - 1 - k][i + k] = true;
            }
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (p[j][i]) {
                    dp[i + 1] = min(dp[i + 1], 1 + dp[j]);
                }
            }
        }
        return dp[N] - 1;
    }
};