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:

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 :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

Leetcode Problem: Climbing Stairs

 Problem of Today: Climbing Stairs

Problem description: https://leetcode.com/problems/climbing-stairs/

Solution Approach: Memoization

Solution: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { private int memo[]; // Bottom-up public int climbStairs(int n) { memo = new int[n+1]; for (int i=0; i<=n; i++) { memo[n] = -1; } memo[0] = 1; memo[1] = 1; for (int i=2; i<=n; i++) { memo[i] = memo[i-1] + memo[i-2]; } return memo[n]; } }

Happy Coding!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder