Description
Count interpretations of a nonempty digit string using codes 1 through 26. A leading zero cannot form a code.
Solution
def num_decodings(s):
before, previous = 1, int(s[0] != '0')
for i in range(1,len(s)):
current = previous if s[i] != '0' else 0
if 10 <= int(s[i-1:i+1]) <= 26:
current += before
before,previous = previous,current
return previousExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["12"]- Output
2
The string can be split as 1|2 or 12.
Example 2
- Input
["06"]- Output
0
A leading zero is invalid.
Example 3
- Input
["2101"]- Output
1
Only 2|10|1 is valid.
Approach
Add the previous state's ways for a valid single digit and the two-back state's ways for a valid pair.
Time & space
O(n) time; O(1) space. Here n is the input length.