Pattern visualizer
Decode Ways
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. Animated on: s = "12120" — 'A'..'Z' map to "1".."26". Count how many different letter strings encode to s..
dp[i] = dp[i-1] (if this digit is a letter) + dp[i-2] (if this pair is)
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.
1FUNCTION decodeWays(s):2 n <- LENGTH(s)3 dp[0] <- 14 FOR i FROM 1 TO n:5 dp[i] <- 06 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