数据结构
网络
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
广告