Let's Code_: interviewBit Medium: Palindrome Partitioning II

Thursday, September 1, 2022

interviewBit Medium: Palindrome Partitioning II

Problem Name: Palindrome Partitioning II

Problem Description: https://www.interviewbit.com/problems/palindrome-partitioning-ii/

Problem Approach used: This problem can be solved with MCM approach. You can note this when you feel the urge to partition the input String into parts (which are palindromes themselves in this case).

Time Complexity: O(n^2) worst-case time complexity and O(n^2) auxiliary space for memoisation.

Solution:

public class Solution {
    public int minCut(String A) {
        
        int memo[][] = new int[502][502];
        for (int i=0; i<502; i++) {
            Arrays.fill (memo[i], -1);
        }
        // i=0, j=n-1 // to ensure 2 partitions
        return palinPartition(A, 0, A.length()-1, memo);
    }
    
    int palinPartition(String A, int i, int j, int [][] memo) {
        if (i >= j) {
            return 0;
        }
        
        if (isPalindrome(A, i, j)) {
            return 0;
        }
        
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        
        int mn = Integer.MAX_VALUE;
        // k= i -> j-1
        for (int k=i; k<j; k++) {
            
            int c1 = palinPartition(A, i, k, memo);
            int c2 = palinPartition(A, k+1, j, memo);
            int temp = c1+c2+1;
            
            mn = Math.min (mn, temp);
        }
        
        return memo[i][j] = mn;
        
    }
    
    boolean isPalindrome(String s, int i, int j) {
        
        if (i >= j)
            return true;
            
        while (i<j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            } else {
                i++;
                j--;
            }
        }
        
        return true;
    }
}