class SolutionR1: # O(n*n) / O(n) ? str slice
def numDecodings(self, s: str) -> int:
m = {'': 1}
def recur(s=s):
if s in m:
return m[s]
m[s] = 0
if s[0] != '0':
m[s] += recur(s[1:])
if 10 <= int(s[:2]) <= 26:
m[s] += recur(s[2:])
return m[s]
return recur()
class SolutionR2: # O(n) / O(n)
def numDecodings(self, s: str) -> int:
m = {len(s): 1}
def recur(i=0):
if i in m:
return m[i]
m[i] = 0
if s[i] != '0':
m[i] += recur(i + 1)
if 10 <= int(s[i : i + 2]) <= 26:
m[i] += recur(i + 2)
return m[i]
return recur()
class Solution1: # O(n) / O(n)
def numDecodings(self, s: str) -> int:
dp = [0] * (len(s) + 1)
dp[0], dp[1] = 1, int(s[0] != '0')
for i in range(len(s) - 1):
if s[i + 1] != '0':
dp[i + 2] += dp[i + 1]
if 10 <= int(s[i : i + 2]) <= 26:
dp[i + 2] += dp[i]
return dp[-1]
class Solution2: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b = 1, int(s[0] != '0')
for i in range(len(s) - 1):
c = 0
if s[i + 1] != '0':
c += b
if 10 <= int(s[i : i + 2]) <= 26:
c += a
a, b = b, c
return b
class Solution3: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b = 1, int(s[0] != '0')
for i in range(len(s) - 1):
one, two = s[i + 1] != '0', 10 <= int(s[i : i + 2]) <= 26
a, b = b, b * one + a * two
return b
class Solution4: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b, p = 0, int(bool(s)), ''
for c in s:
tmp = b
if c == '0':
b = 0
if 10 <= int(p + c) <= 26:
b += a
a, p = tmp, c
return b
class Solution: # O(n) / O(1)
def numDecodings(self, s: str) -> int:
a, b, p = 0, int(bool(s)), ''
for c in s:
one, two = c != '0', 10 <= int(p + c) <= 26
a, b, p = b, b * one + a * two, c
return b
91. Decode Ways - LeetCode
· One min read