class Solution:
"""
@param s: a string, encoded message
@return: an integer, the number of ways decoding
"""
def numDecodings(self, s):
# write your code here
if not s or s == ‘0‘:return 0
dp = [[],[]]
dp[0] = [[s[0]]]
for i in range(1,len(s)):
dp[i%2] = []
index = i%2
for j in range(len(dp[index-1])):
#单独加
if (s[i]!= ‘0‘):
add_d = dp[index-1][j] + [s[i]]
dp[index].append(add_d)
#加尾数
end_num = dp[index-1][j][-1] + s[i]
if (int(end_num) <= 26):
dp[index-1][j][-1] = end_num
dp[index].append(dp[index-1][j])
return len(dp[len(s)%2-1])
注:lintcode未通过,你的代码运行时间超过了限制，检查你的时间复杂度.
class Solution:
"""
@param s: a string, encoded message
@return: an integer, the number of ways decoding
"""
"""
1.最后一步，A-Z之间,只能是f[i-1] + f[i-2]种方法
10-26 且s[i-1] != 0
f[i-1] + f[i-2]
35 这种情况
0 < s[i-1:i] < 10:
f[i-1]
10 or 20
f[i-2]
else
0
"""
def numDecodings(self, s):
if not s or s == ‘0‘:return 0
##123,首个1只是作为12，情况下的1,2和12 这种各一种，12 的方法就是两种
f = [1,1]
for i in range(1,len(s)):
if 10 < int(s[i-1:i+1]) <= 26 and int(s[i]) != 0:
f.append(f[i-1] + f[i])
elif 0 < int(s[i:i+1]) < 10:
f.append(f[i])
elif int(s[i-1:i+1]) == 10 or int(s[i-1:i+1]) == 20:
f.append(f[i-1])
else:
f.append(0)
#f多了一个值,f[len(s)]
return f[len(s)]
