Merge pull request #1259 from larkloss/master

melody-li · web-flow · commit 06e260395d2b · 2019-12-12T18:55:06.000+08:00
436-Week 08
diff --git a/Week 08/id_436/Leetcode_44_436.java b/Week 08/id_436/Leetcode_44_436.java
@@ -0,0 +1,51 @@
+class Solution {
+    public boolean isMatch(String s, String p) {
+        if (s == null || p == null) {
+            return false;
+        }
+        boolean[][] memo = new boolean[s.length()][p.length()];
+        boolean[][] visited = new boolean[s.length()][p.length()];
+        return isMatchHelper(s, 0, p, 0, memo, visited);                
+    }
+    private boolean charMatch(char sChar, char pChar) {
+        return (sChar == pChar || pChar == '?');
+    }    
+    private boolean allStar(String p, int pIndex) {
+        for (int i = pIndex; i < p.length(); i++) {
+            if (p.charAt(i) != '*') {
+                return false;
+            }
+        }
+        return true;
+    }
+    private boolean isMatchHelper(String s, int sIndex,
+                                  String p, int pIndex,
+                                  boolean[][] memo,
+                                  boolean[][] visited) {
+        if (pIndex == p.length()) {
+            return sIndex == s.length();
+        }
+        if (sIndex == s.length()) {
+            return allStar(p, pIndex);
+        }
+                if (visited[sIndex][pIndex]) {
+            return memo[sIndex][pIndex];
+        }
+        
+        char sChar = s.charAt(sIndex);
+        char pChar = p.charAt(pIndex);
+        boolean match;
+        
+        if (pChar == '*') {
+            match = isMatchHelper(s, sIndex, p, pIndex + 1, memo, visited) ||
+                isMatchHelper(s, sIndex + 1, p, pIndex, memo, visited);
+        } else {
+            match = charMatch(sChar, pChar) &&
+                isMatchHelper(s, sIndex + 1, p, pIndex + 1, memo, visited);
+        }
+        
+        visited[sIndex][pIndex] = true;
+        memo[sIndex][pIndex] = match;
+        return match;
+    }
+}
diff --git a/Week 08/id_436/Leetcode_91_436.java b/Week 08/id_436/Leetcode_91_436.java
@@ -0,0 +1,24 @@
+class Solution {
+    public int numDecodings(String s) {
+        if (s.length() == 0) {
+            return 0;
+        }
+        char[] c = s.toCharArray();
+        int[] f = new int[s.length() + 1];
+        f[0] = 1;
+        for (int i = 1; i <= s.length(); ++i) {
+            if (c[i - 1] != '0') {
+                f[i] += f[i - 1];
+            }
+            if (i >= 2) {
+                int val = (c[i - 2] - '0') * 10 +  c[i - 1] - '0';
+                if (10 <= val && val <= 26) {
+                    f[i] += f[i - 2]; 
+                } 
+            }
+        }
+        return f[s.length()];
+    }
+    //in:  0 2 2 6
+    //ou:  1 1 2 4
+}
