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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | 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; } } |
Until Next time, Keep coding and have fun!
Love! ❤️
#Lets #Code
Follow us on :
