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