91. 解码方法
程序员文章站
2022-07-16 09:50:42
...
解
动态规划 + 分情况讨论
前一位 | 当前位 |
---|---|
0 | 0、1-9 |
1 | 0、1-9 |
2 | 0、1-6、7-9 |
class Solution:
def numDecodings(self, s: str) -> int:
s = list(s)
n = len(s)
if s[0] == "0":
return 0
if n == 1:
return 1
if n == 2:
if int(s[0]) == 1:
if int(s[1]) == 0:
return 1
else:
return 2
elif int(s[0]) == 2:
if int(s[1]) == 0:
return 1
elif int(s[1]) <= 6:
return 2
else:
return 1
else:
if int(s[1]) == 0:
return 0
else:
return 1
d = [0 for i in range(n)]
d[0] = 1
if int(s[0]) == 1:
if int(s[1]) == 0:
d[1] = 1
else:
d[1] = 2
elif int(s[0]) == 2:
if int(s[1]) == 0:
d[1] = 1
elif int(s[1]) <= 6:
d[1] = 2
else:
d[1] = 1
else:
if int(s[1]) == 0:
return 0
else:
d[1] = 1
for i in range(2, n):
if int(s[i-1]) == 0:
if int(s[i]) == 0:
return 0
else:
d[i] = d[i-1]
elif int(s[i-1]) == 1:
if int(s[i]) == 0:
d[i] = d[i-2]
else:
d[i] = d[i-2] + d[i-1]
elif int(s[i-1]) == 2:
if int(s[i]) == 0:
d[i] = d[i-2]
elif int(s[i]) <= 6:
d[i] = d[i-2] + d[i-1]
else:
d[i] = d[i-1]
else:
if int(s[i]) == 0:
return 0
else:
d[i] = d[i-1]
return d[n-1]