# 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]

# medium: http://lintcode.com/zh-cn/problem/decode-ways/