資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時裝研究
法律研究Python 中解碼方式
假設我們有一條訊息，其中包含 A 到 Z 的字母，並且按照以下對映將其編碼為數字：'A' → 1, 'B' → 2 ... 'Z' → 26。那麼，如果我們有一個非空字串，只包含數字，那麼我們必須找出可以解碼的可能方式數。所以，如果字串像“12”，那麼這可以由“AB”或“L”構成，所以有兩種可能的方法。因此，答案將是 2。
為了解決這個問題，我們將遵循以下步驟 −
- 我們將使用動態規劃來解決這個問題。
- n := s 的長度
- dp := 一個包含 n 個 0 的陣列
- 如果 s[0] 不等於 '0'，則 dp[0] := 1
- 對於從 1 到 n – 1 的 i
- x := s[i] 作為整數，y := s 的子字串，從索引 i – 1 到 i + 1 作為整數
- 如果 x >= 1 並且 y <= 9，則 dp[i] := dp[i] + dp[i – 1]
- 如果 y >= 10 且 y <= 26
- 如果 i – 2 >= 0，則 dp[i] := dp[i] + dp[i – 2]，否則將 dp[i] 增加 1
- 返回 dp 的最後一個元素
示例（Python）
讓我們看看以下實現，以獲得更好的理解 −
class Solution(object):
def numDecodings(self, s):
n = len(s)
dp = [0 for i in range(n)]
if s[0]!='0':
dp[0]=1
for i in range(1,n):
x = int(s[i])
y = int(s[i-1:i+1])
if x>=1 and x<=9:
dp[i]+=dp[i-1]
if y>=10 and y<=26:
if i-2>=0:
dp[i]+=dp[i-2]
else:
dp[i]+=1
return dp[-1]
ob1 = Solution()
print(ob1.numDecodings("226"))輸入
"226"
輸出
3
更新日期： 2020 年 4 月 28 日
瀏覽量為 954
廣告