Decode Ways
Medium · Dynamic Programming · String · Dynamic Programming
Problem
A message of capital letters was encoded by writing each letter as its position in the alphabet: A is "1", B is "2", and so on up to Z, which is "26". The numbers were written one after another with no separators. Given the digit string s, return how many different messages it could have come from. If it cannot be decoded at all, return 0.
"226" could be 2 2 6 (BBF), 22 6 (VF) or 2 26 (BZ): three messages.
The zeros are the trap. No letter is 0, so a 0 can only be the second digit of 10 (J) or 20 (T). A code never starts with 0: "06" is not F, and "30" is not a letter either. One stranded 0 makes the whole string undecodable, however many ways the rest of it had.
The tests keep the answer below 2^31, as LeetCode promises.
Examples
Input: s = "226" Output: 3
It reads as 2 2 6, 22 6 or 2 26: BBF, VF or BZ.
Input: s = "06" Output: 0
The first digit is 0, and no letter is 0 or starts with 0, so there is no way to begin.
Constraints
- 1 <= len(s) <= 100
- s contains only digits, and may start with 0
- the answer is less than 2^31
Approaches
- Plain recursion, no memory — time O(φ^n) ≈ O(1.62^n), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
