132. Palindrome Partitioning II

Problem Statement

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.

Intuition

Partition the array and if left is palindrome
Recursively check for the later part

Video Links

Approach 1:

Memoization

C++

class Solution {
public:
    bool check_pal(string &s){
        int l = 0, r = s.size()-1;

        while(l<=r){
            if(s[l++] != s[r--])
                return false;
        }

        return true;
    }

    int find_ans(string &s, int index, vector<int> &dp){
        if(index == s.size())
            return 0;

        if(dp[index] != -1)
            return dp[index];

        int mini = INT_MAX;
        string temp = "";

        for(int i=index; i<s.size(); i++){
            temp += s[i];

            if(check_pal(temp)){
                mini = min(1 + find_ans(s, i+1, dp), mini);
            }
        }

        return dp[index] = mini;
    }

    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n, -1);

        return find_ans(s, 0, dp) -1;
    }
};

Approach 2:

Tabulation

Starting from smaller problems and building the answer - Bottom up

Hence starting from n-1

C++

class Solution {
public:
    bool check_pal(string &s){
        int l = 0, r = s.size()-1;

        while(l<=r){
            if(s[l++] != s[r--])
                return false;
        }

        return true;
    }

    int minCut(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);

        for(int k=n-1; k>=0; k--){
            int mini = INT_MAX;
            string temp = "";

            for(int i=k; i<s.size(); i++){
                temp += s[i];

                if(check_pal(temp)){
                    mini = min(1 + dp[i+1], mini);
                }
            }

            dp[k] = mini;
        }


        return dp[0]-1;
    }
};

Approach 3:

C++

Approach 4:

C++