Create decodeWays

kanglicheng · web-flow · commit 03066a192537 · 2018-03-19T00:51:39.000-07:00
diff --git a/Kangli/DP/decodeWays b/Kangli/DP/decodeWays
@@ -0,0 +1,23 @@
+
+
+
+
+
+
+
+O(N) time, O(1) space DP via "general fibonacci numbers"
+class Solution(object):
+    def numDecodings(self, s):
+        if len(s) == 0 or s[0] == '0':
+            return 0
+        prev, prev_prev = 1, 0
+        for i in xrange(len(s)):
+            cur = 0
+            if s[i] != '0':
+                cur = prev
+            if i > 0 and (s[i - 1] == '1' or (s[i - 1] == '2' and s[i] <= '6')):
+                cur += prev_prev
+            prev, prev_prev = cur, prev
+        return prev
+                
+         
