?LeetCode刷題實(shí)戰(zhàn)91：解碼方法
算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問(wèn)題叫做?解碼方法，我們先來(lái)看題面：
https://leetcode-cn.com/problems/decode-ways/
A message containing letters from A-Z is being encoded to numbers using the following mapping:
題意
示例 1：
輸入："12"
輸出：2
解釋：它可以解碼為 "AB"（1?2）或者 "L"（12）。
示例 2：
輸入："226"
輸出：3
解釋：它可以解碼為 "BZ"?(2?26), "VF"?(22?6), 或者 "BBF"?(2?2?6) 。
示例 3：
輸入：s = "0"
輸出：0
示例 4：
輸入：s = "1"
輸出：1
示例 5：
輸入：s = "2"
輸出：1
解題
題解
class?Solution:
????def?numDecodings(self, s: str)?-> int:
????????n = len(s)
????????ret = 0
????????
????????def?dfs(i):
????????????nonlocal?ret
????????????
????????????if?i >= n:
????????????????ret += 1
????????????????return?
????????????
????????????# 當(dāng)前位如果是0則說(shuō)明無(wú)解，return
????????????# 當(dāng)前位為0說(shuō)明上一位不是1或者2
????????????if?s[i] == '0':
????????????????return
????????????
????????????# 遞歸單個(gè)的情況
????????????dfs(i+1)
????????????
????????????# 判斷下一位能否構(gòu)成組合
????????????if?i+1?< n and?(s[i] == '1'?or?(s[i] == '2'?and?ord(s[i+1]) <= ord('6'))):
????????????????dfs(i+2)
????????????????
????????dfs(0)
????????return?ret
class Solution:
????def numDecodings(self, s:?str) -> int:
????????n = len(s)
????????# 為了簡(jiǎn)化判斷，我們把s前面加上0，這樣字符串下標(biāo)從1開(kāi)始
????????s = '0'?+ s
????????dp?= [0?for?_ in range(n+2)]
????????
????????dp[0] = 1
????????for?i in range(1, n+1):
????????????# 如果當(dāng)前位0，那么判斷前一位是否是1或2
????????????# 否則一定無(wú)解
????????????if?s[i] == '0':
????????????????if?i > 1?and?s[i-1] in ('1', '2'):
????????????????????dp[i] = dp[i-2]
????????????????else:
????????????????????return?0
????????????????continue
????????????dp[i] = dp[i-1]
????????????# 能和前一位構(gòu)成字符，那么加上dp[i-2]的數(shù)量
????????????if?i > 1?and?s[i-1] == '1'?or?s[i-1] == '2'?and?ord(s[i]) <= ord('6'):
????????????????dp[i] += dp[i-2]
????????return?dp[n]
總結(jié)
上期推文：