139. Decode Ways
Read the digit string as a sequence of one- or two-digit numbers, with 1 through 26 representing A through Z. Count all ways to decode the entire string.
A token may not begin with zero, and zero has no standalone letter. Different groupings of the same digits may produce different valid decodings.
Example 1
Input
digits="12"
Output
2
Explanation: 1|2 gives AB, and 12 gives L.
Example 2
Input
digits="226"
Output
3
Explanation: 2|2|6, 22|6, and 2|26 are valid.
Example 3
Input
digits="11106"
Output
2
Explanation: 1|1|10|6 and 11|10|6 work; 0 cannot stand alone and 06 is invalid.
Example 4
Input
digits=""
Output
0
Explanation: The public empty-message result differs deliberately from the internal counting identity.
Constraints
0 <= digits.length <= 104- digits contains only ASCII digits 0–9.
Hints
Hint 1
Classify complete tokenizations by the width of their final token.
Hint 2
What predecessor is used for a valid 10 pair, and why must the empty prefix contribute one?
Hint 3
Add old D(k−1) only for a nonzero last digit and old D(k−2) only for pairs 10..26.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Both final-token widths can contribute
"226"
"3"