91, dp

chaor · chaor · commit 3af7680f9135 · 2016-03-28T22:38:28.000-07:00
diff --git a/91_Decode_Ways.py b/91_Decode_Ways.py
@@ -1,15 +1,16 @@
-# 2015-04-08  Runtime: 54 ms
-
-class Solution:
-    # @param s, a string
-    # @return an integer
+# 2016-03-28   259 tests, 64 ms
+class Solution(object):
     def numDecodings(self, s):
+        """
+        :type s: str
+        :rtype: int
+        """
         if not s: return 0
-        # dp[M] means decode ways for first M letters of s
-        dp = [0 for i in xrange(len(s) + 1)]
-        dp[0] = 1
-        dp[1] = 0 if s[0] == '0' else 1
-        for i in xrange(2, len(s) + 1):
-            if s[i-1] != '0': dp[i] += dp[i-1]
-            if 10 <= int(s[i-2:i]) <= 26: dp[i] += dp[i-2]
-        return dp[len(s)]
+        len_s = len(s)
+        dp = [1] + [0] * len_s
+        for i in xrange(1, len_s + 1):
+            if s[i - 1] != '0':
+                dp[i] += dp[i - 1]
+            if i >= 2 and 10 <= int(s[i - 2: i]) <= 26:
+                dp[i] += dp[i - 2]
+        return dp[len_s]
