Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Decode Ways

LeetCode #91Medium
1 or 2 digits at a time

Letters A through Z map to the codes 1 through 26. Given a string of digits, return the number of distinct ways it can be decoded back into letters.

Asked atAmazonMetaGoogleUber
step 1 / 7
2
2
6
[0][1][2]
dp
·
·
·
·
[0][1][2][3]
DP over prefixes
▸
1def numDecodings(s):
2    dp = [0] * (n + 1)
3    dp[0] = 1               # empty prefix: one way
4    for i in 1..n:
5        if s[i−1] != '0':   # one-digit letter
6            dp[i] += dp[i−1]
7        if i >= 2 and 10 <= int(s[i−2:i]) <= 26:
8            dp[i] += dp[i−2]   # two-digit letter
9    return dp[n]
state
  • s"226"
  • asknumber of decodings

line 1Decode Ways: letters A..Z are encoded as "1".."26". Given the digit string "226", count how many distinct decodings exist. The top row is the digits; the dp row (length n+1) counts ways for each prefix.