91. 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码:
‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 给定一个只包含数字的非空字符串,请计算解码方法的总数。
题目数据保证答案肯定是一个 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
示例 4:
输入:s = "1"
输出:1
示例 5:
输入:s = "2"
输出:1
提示:
1 <= s.length <= 100
s 只包含数字,并且可能包含前导零。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-ways/
Link:https://leetcode.com/problems/decode-ways/
递归 + 记忆化搜索
由于python的强大,加一个lru_cache就可以了
动态规划的本质是,从一个方向递推,防止重复计算,所以递归+记忆化搜索,也是一种动态规划
from functools import lru_cache
class Solution:
@lru_cache(maxsize=None)
def numDecodings(self, s: str) -> int:
if len(s) == 0 or s[0] == '0':
return 0
if len(s) == 1 and 1 <= int(s[0]) <= 9:
return 1
if len(s) == 2 and 10 <= int(s[0:2]) <= 26:
return 1 if s[-1] == '0' else 2
count = 0
if 1 <= int(s[-1]) <= 9: # 末尾一个字符
count += self.numDecodings(s[:-1]) # 去掉末尾一个字符
if 10 <= int(s[-2:]) <= 26: #末尾两个字符
count += self.numDecodings(s[:-2]) # 去掉末尾两个字符
return count
代码是对称的
from functools import lru_cache
class Solution:
@lru_cache(maxsize=None)
def numDecodings(self, s: str) -> int:
if len(s) == 0 or s[0] == '0':
return 0
if len(s) == 1 and 1 <= int(s[0]) <= 9:
return 1
if len(s) == 2 and 10 <= int(s[0:2]) <= 26:
return 1 if s[-1] == '0' else 2
count = 0
if 1 <= int(s[0]) <= 9: # 前一个字符
count += self.numDecodings(s[1:]) # 去掉前一个字符
if 10 <= int(s[:2]) <= 26: # 前两个字符
count += self.numDecodings(s[2:]) # 去掉前两个字符
return count
动态规划
状态定义
dp[i]代表前i个字符串有多少种解码方式
状态方程
如果最后数字,可以作为1位数解码(1-9)
table[i] += table[i - 1]
如果最后两位数,可以作为2位数解码(10-26)
table[i] += table[i - 2]
计算方向
从第二个开始,从小到大计算
边界条件
如果第一个数字为0
table[0] = table[1] = 0
相反
table[0] = table[1] = 1
代码实现
class Solution:
def numDecodings(self, s: str) -> int:
dp = [0 for i in range(len(s) + 1)]
dp[0] = dp[1] = 0 if s[0] == '0' else 1
for i in range(2, len(s) + 1):
if s[i - 1] != '0':
dp[i] += dp[i - 1]
if (s[i - 2] == '1' and s[i - 1] in '0123456789') or (s[i - 2] == '2' and s[i - 1] in '0123456'):
dp[i] += dp[i - 2]
return dp[-1]
–End–