Q23 Palindrome Partitioning II - LeetCode 132
Fri Mar 24 2023 14:29:54 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int minCut(String s) {
/* dp playlist video 28 , 2nd approach O(n^2)
*/
//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;
}
}
}
//making 1d dp array
int dp[] = new int [n];
dp[0] = 0; //0 letters need no cuts
//now checking every suffix from
for(int i = 1 ; i < n ; i++){
int min = Integer.MAX_VALUE;
//making suffix and checking from boolean table
for(int j = i ; j >= 0 ;j-- ){
//if suffix is already a pallindrome
if(j==0 && arr[j][i])
min = 0;
else if(arr[j][i])
min = Math.min(min , dp[j-1] + 1);
}
dp[i] = min;
}
return dp[n-1];
}
}
content_copyCOPY
https://leetcode.com/problems/palindrome-partitioning-ii/
Comments