Decode Ways
Problem
Letters A–Z are encoded as the numbers 1–26. Given a string of digits, count how many ways it can be split into valid codes and decoded back into letters. A code cannot have a leading zero, so "06" is not valid.
Examples
Constraints
- • 1 <= s.length <= 100
- • s contains only digits
Hints & approach
Hint 1
At each position you can consume one digit or two digits.
Hint 2
A single digit is valid only if it is not 0; a pair is valid if it is between 10 and 26.
Hint 3
ways[i] = (s[i-1] valid ? ways[i-1] : 0) + (s[i-2..i-1] valid ? ways[i-2] : 0).
Approachtry the hints first
Let ways[i] be the number of decodings of the first i characters, with ways[0] = 1 for the empty prefix. The last code is either one digit (valid when it is 1–9), contributing ways[i-1], or two digits (valid when they form 10–26), contributing ways[i-2]. Sum the valid contributions. Only two previous values are needed, so the space collapses to constant.
Time O(n) · Space O(1)