Skip to content

Instantly share code, notes, and snippets.

@Desolve

Desolve/0091 Decode Ways.py

Created January 14, 2020 16:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Desolve/51589115429e6a36335017a990c03510 to your computer and use it in GitHub Desktop.
Save Desolve/51589115429e6a36335017a990c03510 to your computer and use it in GitHub Desktop.
Download ZIP
0091 Decode Ways
Raw
0091 Decode Ways.py
class Solution:
def numDecodings(self, s: str) -> int:
if not s: return 0
l = len(s)
dp = [0] * (l+1)
dp[0], dp[1] = 1, 1 if s[0] != "0" else 0
prev, curr = "0", s[0]
for i in range(2, l + 1):
prev = curr
curr = s[i-1]
if curr != "0":
dp[i] += dp[i-1]
if prev == "1" or prev == "2" and curr <= "6":
dp[i] += dp[i-2]
return dp[l]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment