来源:力扣(LeetCode)
链接:https://leetcode.com/problems/decode-ways
这道题很明显要用动态规划,但是状态转移方程看上去比较复杂,因为有0
的存在。比如,如果存在连续包含两个0
的情况,则必然输出0
;再比如,如果出现类似于80
的情况,也必然输出0
。
以下状态转移方程,可以完美解决这个问题。
-
1 <= s[i] <= 9
。则ans[i+1] += ans[i]
; -
10 <= s[i-1]s[i] <= 26
。则ans[i+1] += ans[i-1]
; - 如果以上两个都不成立,则
s[i]
必然是0
,且无法和s[i-1]
组成10
或者20
,则意味着该字符串无法表示有效字符,直接输出0
,结束运行。
再看初始值,为什么要把ans[0]
设为1
呢?因为如果s[0]s[1] = 10
,则ans[2] = ans[0]
,而ans[2]
应该是1
。
完整代码:
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
elif len(s) == 1:
return 1
ans = [None for _ in range(len(s)+1)]
ans[0] = 1 #这个初值很重要
ans[1] = 1
for i in range(1, len(s)):
ans[i+1] = 0
succ = 0
if int(s[i])>=1 and int(s[i])<=9:
ans[i+1] += ans[i]
succ = 1
if int(s[i-1] + s[i])>=10 and int(s[i-1] + s[i])<=26:
ans[i+1] += ans[i-1]
succ = 1
if succ == 0:
return 0
return ans[len(s)]
运行结果: