DSA Tracker

Visualize

Decode Ways

dp[i] = dp[i-1] (if this digit is a letter) + dp[i-2] (if this pair is)

time O(n)space O(n)

Read the string left to right and ask only one question at each position: what was the LAST letter? It used one digit or two, and nothing else is possible, so the count of decodings ending here is the count of decodings of everything before that letter. That makes dp[i] = dp[i-1] + dp[i-2], with each term dropped when it does not spell a letter — a lone '0' is not a letter, and a pair is only a letter when it reads 10 to 26. The leading-zero rule is what kills "07": 7 is a letter but "07" is not a number.

Details

Animated on: s = "12120" — 'A'..'Z' map to "1".."26". Count how many different letter strings encode to s.

Problem:Decode WaysMedium

dp[i] = dp[i-1] (if this digit is a letter) + dp[i-2] (if this pair is)

step 1 / 11

dp over "12120" — dp[i] = ways to decode the first i characters

dp[0] = 1: the empty prefix has exactly one decoding — the empty one. Every later count is built out of this, so it must be 1, not 0.

Pseudocode
1FUNCTION decodeWays(s):
2  n <- LENGTH(s)
3  dp[0] <- 1
4  FOR i FROM 1 TO n:
5    dp[i] <- 0
6    IF s[i-1] != '0':
7      dp[i] <- dp[i] + dp[i-1]
8    IF i >= 2 AND s[i-2] != '0' AND NUMBER(s[i-2..i-1]) <= 26:
9      dp[i] <- dp[i] + dp[i-2]
10  RETURN dp[n]

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. dp[0] = 1: the empty prefix has exactly one decoding — the empty one. Every later count is built out of this, so it must be 1, not 0.
  2. '1' is a letter on its own (1-9), so every decoding of the first 0 characters extends by one letter: dp[1] += dp[0] = 1.
  3. '2' is a letter on its own (1-9), so every decoding of the first 1 characters extends by one letter: dp[2] += dp[1] = 1.
  4. "12" is 12 <= 26, so those two digits can also be read as one letter: dp[2] += dp[0] = 1, giving dp[2] = 2.
  5. '1' is a letter on its own (1-9), so every decoding of the first 2 characters extends by one letter: dp[3] += dp[2] = 2.
  6. "21" is 21 <= 26, so those two digits can also be read as one letter: dp[3] += dp[1] = 1, giving dp[3] = 3.
  7. '2' is a letter on its own (1-9), so every decoding of the first 3 characters extends by one letter: dp[4] += dp[3] = 3.
  8. "12" is 12 <= 26, so those two digits can also be read as one letter: dp[4] += dp[2] = 2, giving dp[4] = 5.
  9. '0' decodes to nothing on its own — there is no letter 0 — so dp[4] = 5 contributes nothing. Only a two-digit pair can rescue this position.
  10. "20" is 20 <= 26, so those two digits can also be read as one letter: dp[5] += dp[3] = 3, giving dp[5] = 3.
  11. dp[5] = 3 — the whole string "12120" has 3 decodings. The 0 forced every one of them to end in "20", which is why the count never grew past dp[3].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Decode Ways in the editorAll Dynamic Programming problemsBack to roadmap