# LeetCode 91. 解码方法

2021-08-08 00:12:25 ZSYL

# 题目描述

'A' -> 1
'B' -> 2
...
'Z' -> 26


• “AAJF” ，将消息分组为 (1 1 10 6)
• “KJF” ，将消息分组为 (11 10 6)

输入：s = "12"



# 参考代码

## Java

class Solution {

public int numDecodings(String s) {

int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; ++i) {

if (s.charAt(i - 1) != '0') {

dp[i] += dp[i - 1];
}
if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {

dp[i] += dp[i - 2];
}
}
return dp[n];
}
}


class Solution {

public int numDecodings(String s) {

int n = s.length();
// a = f[i-2], b = f[i-1], c=f[i]
int a = 0, b = 1, c = 0;
for (int i = 1; i <= n; ++i) {

c = 0;
if (s.charAt(i - 1) != '0') {

c += b;
}
if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {

c += a;
}
a = b;
b = c;
}
return c;
}
}


## Python

class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
dp = [1] + [0] * n
for i in range(1, n + 1):
if s[i - 1] != '0':
dp[i] += dp[i - 1]
if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
dp[i] += dp[i - 2]
return dp[n]

class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
# a = f[i-2], b = f[i-1], c = f[i]
a, b, c = 0, 1, 0
for i in range(1, n + 1):
c = 0
if s[i - 1] != '0':
c += b
if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
c += a
a, b = b, c
return c


• 时间复杂度：O(n)，其中 nn 是字符串 ss 的长度。
• 空间复杂度：O(n) 或 O(1)。如果使用数组进行状态转移，空间复杂度为 O(n)；如果仅使用三个变量，空间复杂度为 O(1)。

https://blog.csdn.net/qq_46092061/article/details/119493537