[Leetcode] Decode Ways – python

2017年01月10日 ⁄ 综合 ⁄ 共 928字 ⁄ 字号 评论关闭

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.

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

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

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

```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')```