class Solution:
def numDecodings(self, s: str) -> int:
pp, p = 1, int(s[0] != "0")
for i in range(1, len(s)):
pp, p = p, pp*(9 < int(s[i-1:i+1]) <= 26)+p*(int(s[i]) > 0)
return p
Runtime: 28 ms, faster than 83.56% of Python3 online submissions for Decode Ways.
Memory Usage: 12.5 MB, less than 100.00% of Python3 online submissions for Decode Ways.
class Solution:
def numDecodings(self, s: str) -> int:
v, w, p = 0, int(s > ""), ""
for d in s:
v, w, p = w, (d > "0")*w+(9 < int(p+d) < 27)*v, d
return w
Runtime: 28 ms, faster than 83.56% of Python3 online submissions for Decode Ways.
Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Decode Ways.
递归
class Solution:
def numDecodings(self, s: str) -> int:
def recu(i):
if i == len(s):
return 1
if s[i] == '0':
return 0
ans1 = recu(i+1)
ans2 = 0
if i < len(s)-1:
if int(s[i]+s[i+1]) <= 26:
ans2 = recu(i+2)
return ans1+ans2
return recu(0)
超时了
带备忘录的递归
class Solution:
def numDecodings(self, s: str) -> int:
memo = {}
def recu(i):
if i == len(s):
return 1
if s[i] == '0':
return 0
if i in memo:
return memo[i]
ans1 = recu(i+1)
ans2 = 0
if i < len(s)-1:
if int(s[i]+s[i+1]) <= 26:
ans2 = recu(i+2)
memo[i] = ans1 + ans2
return ans1+ans2
return recu(0)
Runtime: 36 ms, faster than 27.57% of Python3 online submissions for Decode Ways.
Memory Usage: 13.7 MB, less than 16.00% of Python3 online submissions for Decode Ways.
自底向上
class Solution:
def numDecodings(self, s: str) -> int:
if not s:
return 0
n = len(s)
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1 if s[0] != '0' else 0
for i in range(2, n+1):
first = int(s[i-1:i])
second = int(s[i-2:i])
if first >= 1 and first <= 9:
dp[i] += dp[i-1]
if second >= 10 and second <= 26:
dp[i] += dp[i-2]
return dp[n]
Runtime: 32 ms, faster than 59.69% of Python3 online submissions for Decode Ways.
Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Decode Ways.