Skip to content

Latest commit

 

History

History
65 lines (52 loc) · 1.87 KB

132. Palindrome Partitioning II.md

File metadata and controls

65 lines (52 loc) · 1.87 KB

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 lower-case English letters only.

class Solution {
    public int minCut(String s) {
        boolean[][] isPal=computePalindromes(s);  
        if(isPal[0][s.length()-1]) return 0;
        int cuts[]=new int[s.length()];
        /*
        Role of the following loop: With outer loop we are selecting a letter and then we compare it with each letter before it
        and see if we need to make a cut or not. consider "aab"
        we are on second 'a' with outer loop 
        so when inner loop runs we  check if aa is palindrome or not. If yes, then we check if j==0 if that's the case then we 
        don't need to make any cut there. So we don't make any cut there but if we arent' on start then we have to make a cut here
        so total cuts would be cuts[j-1] +1 which is nothing but cuts done before this cut + 1
        */
        for(int i=0;i<s.length();i++){
            int min=i;
            for(int j=0;j<=i;j++){
                if(isPal[j][i]){
                    min=j==0?0:Math.min(min,cuts[j-1]+1);
                }
            }
            cuts[i]=min;
        }
        return cuts[cuts.length-1];
    }  
    public boolean[][] computePalindromes(String s){
        boolean[][] res=new boolean[s.length()][s.length()];
        for(int i=0;i<s.length();i++){
            for(int j=0;j<=i;j++){
                if(s.charAt(j)==s.charAt(i) && (j+1>i-1 || res[j+1][i-1]))
                    res[j][i]=true;
            }
        }
        return res;
    }
}