Leetcode91. Decode Ways-递归
题目
思路
假设字符串长度为N,
用递归来缩减问题规模,有两个方向:
- 从前到后
每个位置有两种可能解码:
takeOne:取前1个字符,则解码方案数与后面N-1个字符的方案数相同
takeTwo:取前2个字符,则解码方案数与后面N-2个字符的方案数相同
总解码数为takeOne+takeTwo - 从后到前
每个位置有两种可能解码:
takeOne:取最后1个字符,则解码方案数与前面N-1个字符的方案数相同
takeTwo:取最后2个字符,则解码方案数与前面N-2个字符的方案数相同
总解码数为takeOne+takeTwo
实现差异
只是每次递归对字符串的切片方向不同,其他代码完全共用
前向:s[:1],s[:2]
后向:s[-1:],s[-2:]
复杂度
- 时间复杂度
O
(
N
)
\mathcal{O}(N)
O(N)
从前到后一次递归 - 空间复杂度
O
(
N
2
)
\mathcal{O}(N^2)
O(N2)
每次递归使用的是字符串的切片,从N到1: ∑ i = 1 N i \sum_{i=1}^{N}i ∑i=1Ni
从前到后
class Solution:
def numDecodings(self, s: str) -> int:
self.memo = {}
return self.decode(s)
def decode(self, s: str) -> int:
if len(s) == 0: return 1
if s in self.memo: return self.memo[s]
takeOne = takeTwo = 0
if 1 <= int(s[:1]) <= 9:
takeOne = self.decode(s[1:])
if 10 <= int(s[:2]) <= 26:
takeTwo = self.decode(s[2:])
self.memo[s] = takeOne + takeTwo
return self.memo[s]
从后到前
class Solution:
def numDecodings(self, s: str) -> int:
self.memo = {}
return self.decode(s)
def decode(self, s: str) -> int:
if len(s) == 0: return 1
if s in self.memo: return self.memo[s]
takeOne = takeTwo = 0
if 1 <= int(s[-1:]) <= 9:
takeOne = self.decode(s[:-1])
if 10 <= int(s[-2:]) <= 26:
takeTwo = self.decode(s[:-2])
self.memo[s] = takeOne + takeTwo
return self.memo[s]