Accepted

Goutham Pradhan · Goutham Pradhan · commit 1b13c00202fa · 2017-04-03T18:08:16.000+02:00
diff --git a/problems/src/HouseRobber.java b/problems/src/HouseRobber.java
@@ -0,0 +1,31 @@
+/**
+ * Created by pradhang on 4/3/2017.
+ * Accepted
+ */
+public class HouseRobber
+{
+    private int[] max;
+    /**
+     * Main method
+     * @param args
+     * @throws Exception
+     */
+    public static void main(String[] args) throws Exception
+    {
+
+    }
+
+    public int rob(int[] nums)
+    {
+        if(nums.length == 0) return 0;
+        max = new int[nums.length];
+        if(nums.length == 1) return nums[0];
+        max[nums.length - 1] = nums[nums.length - 1];
+        max[nums.length - 2] = Math.max(nums[nums.length - 1], nums[nums.length - 2]);
+        for(int i = nums.length - 3; i >= 0; i --)
+        {
+            max[i] = Math.max(max[i + 1], nums[i] + max[i + 2]);
+        }
+        return max[0];
+    }
+}
diff --git a/problems/src/PalindromePartitioningII.java b/problems/src/PalindromePartitioningII.java
@@ -0,0 +1,62 @@
+import java.util.Arrays;
+
+/**
+ * Created by pradhang on 4/3/2017.
+ * Accepted
+ */
+public class PalindromePartitioningII
+{
+    private int A[];
+    private boolean[][] paliandrome;
+    /**
+     * Main method
+     * @param args
+     */
+    public static void main(String[] args)
+    {
+        System.out.println(new PalindromePartitioningII().minCut("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
+    }
+
+    public int minCut(String s)
+    {
+        if(s == null || s.isEmpty()) return 0;
+        A = new int[s.length()];
+        Arrays.fill(A, Integer.MAX_VALUE);
+        char[] charArr = s.toCharArray();
+        paliandrome = new boolean[charArr.length][charArr.length];
+        return doNext(charArr, 0) - 1;
+    }
+
+    private int doNext(char[] s, int p)
+    {
+        if(p >= s.length) return 0;
+        if(A[p] < Integer.MAX_VALUE) return A[p];
+        for(int i = p, l = s.length; i < l; i ++ )
+        {
+            if(p + 1 <= i - 1) {
+                paliandrome[p][i] = paliandrome[p + 1][i - 1] && (s[p] == s[i]) || isPalindrome(s, p, i);
+            }
+            else
+            {
+                paliandrome[p][i] = isPalindrome(s, p, i);
+            }
+            if(paliandrome[p][i])
+            {
+                A[p] = Math.min(doNext(s, i + 1) + 1, A[p]);
+            }
+        }
+        return A[p];
+    }
+
+    private boolean isPalindrome(char[] sb, int s, int e)
+    {
+        while(s <= e)
+        {
+            if(sb[s] != sb[e])
+                return false;
+            s++; e--;
+        }
+        return true;
+    }
+
+}
