学步园

A message containing letters from A-Z is being encoded to numbers using
the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message "12", it could be decoded as "AB" (1
2) or "L" (12).

The number of ways decoding "12" is 2.

这一道完全是细节题，简单列举几个数据，如'00','0','1212','1234'之后，即可推出规律：

从后向前处理，假如处理到第i位，

1、假如当前位和后一位均为0，则返回0

2、当前位和后一位不能组合，如'34'，那么counts[i]=counts[i+1]

3、当前位和后一位可以组合，则counts[i]=counts[i+1]+counts[i+2]

初始化counts[len(s)]=1

代码如下：

class Solution:
    # @param s, a string
    # @return an integer
    def numDecodings(self, s):
        if len(s)<1 or s[0]=='0':
            return 0
        counts={}
        counts[len(s)]=1
        if s[-1]=='0':
            counts[len(s)-1]=0
        else:
            counts[len(s)-1]=1
        for i in xrange(len(s)-2,-1,-1):
            if s[i]=='0' :
                if s[i+1]=='0':
                    return 0
                else:
                    counts[i]=0
            elif int(s[i])<3 and int(s[i])>0 and int(s[i:i+2])<27 and int(s[i:i+2])>0:
                counts[i]=counts[i+2]+counts[i+1]
            else:
                counts[i]=counts[i+1]
        return counts[0]

a=Solution()
print a.numDecodings('10')