解码方法

yingl · yingl · commit e57869437287 · 2016-08-02T15:21:36.000+08:00
diff --git a/decode_ways.py b/decode_ways.py
@@ -0,0 +1,24 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param {string} s a string,  encoded message
+    # @return {int} an integer, the number of ways decoding
+    def numDecodings(self, s):
+        # Write your code here
+        '''
+        从后往前找，对于第i位的情况：
+        1. 等于第i + 1位的组合。
+        2. 如果s[i][i + 1]在10到26的范围内，再加上第i + 2位的组合。
+        '''
+        if not s:
+            return 0
+        cached_nums = [1 for i in xrange(len(s) + 1)] # 多一格方便处理倒数第二位的情况
+        for i in xrange(len(s) - 1, -1, -1):
+            if s[i] == '0':
+                cached_nums[i] = 0
+            else:
+                cached_nums[i] = cached_nums[i + 1]
+            if i < len(s) - 1:
+                if (s[i] == '1') or ((s[i] == '2') and (s[i + 1] <= '6')):
+                    cached_nums[i] += cached_nums[i + 2]
+        return cached_nums[0]
