class Solution { public int minCut(String s) { /* dp playlist video 28 , first approach O(n^3) */ //make boolean 2d array int n = s.length(); boolean[][] arr = new boolean[n][n]; //traversing diagonally up for(int gap = 0 ; gap < n ; gap++){ for(int i = 0 , j = gap ; j < n ; i++ , j++){ if(gap == 0) arr[i][j] = true; else if(gap == 1){ if(s.charAt(i) == s.charAt(j)) arr[i][j] = true; } else{ if(s.charAt(i) == s.charAt(j) && arr[i+1][j-1]==true) arr[i][j] = true; } } } //now making int 2d array to store minimum cuts on every cell int [][] dp = new int[n][n]; for(int gap = 0 ; gap < n ; gap++){ for(int i = 0 , j = gap ; j < n ; i++ , j++){ //handling trivial cases if(gap == 0) dp[i][j] = 0; else if(gap == 1){ if(s.charAt(i) != s.charAt(j)) dp[i][j] = 1; } else{ //if word is already a pallindrome if(arr[i][j] == true) dp[i][j] = 0; else{ /* now checking every partion call for minimum cuts(faith) left string will be [i , k] right will be [k+1 , j] find minimum cut faith call */ int min = Integer.MAX_VALUE; //k starts from i and ends on j for(int k = i ; k < j ;k++){ int left = dp[i][k]; int right = dp[k+1][j]; min = Math.min(min,left + right); } dp[i][j] = min +1; //add 1 for faith call } } } } return dp[0][n-1]; //last coloumn of first row will have answer } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter