Update decodeWays.py

kanglicheng · web-flow · commit 35a75a47b83a · 2018-03-19T00:53:01.000-07:00
diff --git a/Kangli/DP/decodeWays.py b/Kangli/DP/decodeWays.py
@@ -1,11 +1,20 @@
+#first solution, O(N) time and space
+class Solution(object):
+    def numDecodings(self, s):
+        if not s:
+            return 0
+        dp = [0]*(len(s)+1)
+        dp[0] = 1 
+        for i in range(1, len(s)+1):
+            if s[i-1] != '0':
+                dp[i] += dp[i-1]
+            if i != 1:
+                if int(s[i-2:i]) in range(10, 27):
+                    dp[i] += dp[i-2]
+        return dp[len(s)]
 
-
-
-
-
-
-
-O(N) time, O(1) space DP via "general fibonacci numbers"
+    
+#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':
