update 91

fishercoder1534 · fishercoder1534 · commit e38f140f8533 · 2021-07-14T13:04:09.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_91.java b/src/main/java/com/fishercoder/solutions/_91.java
@@ -1,5 +1,8 @@
 package com.fishercoder.solutions;
 
+import java.util.HashMap;
+import java.util.Map;
+
 public class _91 {
     /**
      * Credit: https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation
@@ -31,4 +34,40 @@ public int numDecodings(String s) {
             return dp[s.length()];
         }
     }
+
+    public static class Solution2 {
+        /**credit: https://leetcode.com/problems/decode-ways/solution/
+         * Approach 1: Recursive Approach with Memoization
+         *
+         * The actual code goes from the right most character to the left side to build out the dp cache map.
+         * And this HashMap uses index as its key instead of a substring.
+         * */
+
+        public int numDecodings(String s) {
+            return dp(new HashMap<>(), s, 0);
+        }
+
+        private int dp(Map<Integer, Integer> cache, String s, int index) {
+            if (cache.containsKey(index)) {
+                return cache.get(index);
+            }
+            if (index == s.length()) {
+                //this means we reached the end of the string, so return 1 as success
+                return 1;
+            }
+            if (s.charAt(index) == '0') {
+                //this means this string cannot be decoded
+                return 0;
+            }
+            if (index == s.length() - 1) {
+                return 1;
+            }
+            int ways = dp(cache, s, index + 1);
+            if (Integer.parseInt(s.substring(index, index + 2)) <= 26) {
+                ways += dp(cache, s, index + 2);
+            }
+            cache.put(index, ways);
+            return cache.get(index);
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_91Test.java b/src/test/java/com/fishercoder/_91Test.java
@@ -8,15 +8,24 @@
 
 public class _91Test {
     private static _91.Solution1 solution1;
+    private static _91.Solution2 solution2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _91.Solution1();
+        solution2 = new _91.Solution2();
     }
 
     @Test
     public void test1() {
         assertEquals(2, solution1.numDecodings("12"));
+        assertEquals(2, solution2.numDecodings("12"));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(1, solution1.numDecodings("10"));
+        assertEquals(1, solution2.numDecodings("10"));
     }
 
 }
