Decode Ways
Hard · rating 1800 · Dynamic Programming, Strings
A message of digits is encoded with A=1, B=2, …, Z=26. Read the digit string and print the number of ways to decode it. A leading 0 or an invalid pair makes zero ways.
For 226 the answer is 3 (BZ, VF, BBF).
Constraints: 1 ≤ length ≤ 1000
Editorial
Approach
A digit-string DP: ways(i) is the number of decodings of the suffix starting at i. Each step, a non-zero single digit contributes ways(i+1), and a valid two-digit pair (10–26) contributes ways(i+2). Roll it up from the end with two variables.
The zero traps
A 0 can't stand alone, so it only survives as the second digit of 10 or 20; anything else makes that position contribute nothing.
prev2 = prev1 = 1
for i in range(1, n):
cur = 0
if s[i] != '0': cur += prev1
if 10 <= int(s[i-1:i+1]) <= 26: cur += prev2
prev2, prev1 = prev1, curComplexity
Time: O(n). Space: O(1).
Related problems
- Edit Distance — Hard
- Word Break — Hard
- Longest Common Subsequence — Hard
- Longest Common Substring — Hard
- Longest Palindromic Substring — Hard
- Longest Valid Parentheses — Hard