GeezerVison is showing github.com — leetcode/91_num_decoding.py at main · StriveInDecember/leetcode

Expand file tree

91_num_decoding.py

Copy path

More file actions

Latest commit

History

86 lines (83 loc) · 2.06 KB

91_num_decoding.py

Copy path

File metadata and controls

86 lines (83 loc) · 2.06 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

# 一条包含字母 A-Z 的消息通过以下映射进行了编码：

# 'A' -> 1

# 'B' -> 2

# ...

# 'Z' -> 26

# 要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

# "AAJF" ，将消息分组为 (1 1 10 6)

# "KJF" ，将消息分组为 (11 10 6)

# 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

# 给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。

# 题目数据保证答案肯定是一个 32 位的整数。

# 示例 1：

# 输入：s = "12"

# 输出：2

# 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

# 示例 2：

# 输入：s = "226"

# 输出：3

# 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

# 示例 3：

# 输入：s = "0"

# 输出：0

# 解释：没有字符映射到以 0 开头的数字。

# 含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。

# 由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

# 示例 4：

# 输入：s = "06"

# 输出：0

# 解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

# 提示：

# 1 <= s.length <= 100

# s 只包含数字，并且可能包含前导零。

# Related Topics 字符串动态规划

# 👍 776 👎 0

# leetcode submit region begin(Prohibit modification and deletion)

class Solution:

def numDecodings(self, s: str) -> int:

n = len(s)

s = " " + s

f = [0] * (n + 1)

f[0] = 1

for i in range(1, n + 1):

a = ord(s[i]) - ord("0")

b = (ord(s[i - 1]) - ord("0")) * 10 + a

if 1 <= a <= 9:

f[i] = f[i - 1]

if 10 <= b <= 26:

f[i] += f[i - 2]

return f[-1]

# leetcode submit region end(Prohibit modification and deletion)