描述

有一個(gè)消息包含A-Z通過以下規(guī)則編碼

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
現(xiàn)在給你一個(gè)加密過后的消息，問有幾種解碼的方式

我們不能解碼空串，因此若消息為空，你應(yīng)該返回0。
消息的長度 n \leq 100n≤100

您在真實(shí)的面試中是否遇到過這個(gè)題？
樣例
樣例 1:

輸入: “12”
輸出: 2
解釋: 它可以被解碼為 AB (1 2) 或 L (12).
樣例 2:

輸入: “10”
輸出: 1

思路
動(dòng)態(tài)規(guī)劃，從s的位置1讀起，每次讀取兩個(gè)數(shù)，因?yàn)橹灰?-9的數(shù)，都可以單獨(dú)出現(xiàn)，因此，dp表可以初始化為1，為了避免第二個(gè)條件[i-1]無法執(zhí)行，我們使得dp表從位置2開始修改，dp位置0，1的值都初始化為1

情況
#特殊情況 輸入’’ 則無法解碼，可直接返回 0
#輸入0 則無法解碼，可直接返回 0
#若為 00 或 30、40、50… 則無法解碼，可直接返回 0
#為 10、20 的情況，則 i 處字符必須與前一位結(jié)合，則為雙字符解碼
dp[i + 1] = dp[i - 1]
若數(shù)字為10-26：既可以單字解碼，又可以雙字解碼 dp[i + 1] = dp[i] + dp[i - 1]
#1-9，27-29、31-39、41~49…只能單字解碼 dp[i + 1] = dp[i]

class Solution:def numDecodings(self, s):if len(s)==0: return 0 #特殊情況 輸入'' 則無法解碼，可直接返回 0if s[0]=="0":return 0 #輸入0 則無法解碼，可直接返回 0dp = [0] * (len(s) + 1)dp[0],dp[1]=1,1for i in range(1, len(s)):if s[i] == '0':if int(s[i - 1]) > 2 or int(s[i - 1]) == 0: #若為 00 或 30、40、50... 則無法解碼，可直接返回 0；return 0dp[i + 1] = dp[i - 1] #為 10、20 的情況，則 i 處字符必須與前一位結(jié)合，則為雙字符解碼elif 9 < int(s[i - 1:i + 1]) < 27:dp[i + 1] = dp[i] + dp[i - 1] #既可以單字解碼，又可以雙字解碼else:dp[i + 1] = dp[i]#1-9，27~29、31~39、41~49....只能單字解碼return dp[-1] test = Solution() s_li = ["9", "226", "300"] for s in s_li:print(test.numDecodings(s))

結(jié)果：
1
3
0

總結(jié)

以上是生活随笔為你收集整理的leetcode解码方法（动态规划python）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。