A message containing letters A-Z is encoded where A = 1, B = 2, ..., Z = 26. Given a string of digits, determine the total number of ways to decode it.
For example, given "226", there are 3 ways: "BZ" (2, 26), "VF" (22, 6), "BBF" (2, 2, 6).
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
Process the string one digit at a time. At each position, consider whether you can decode one digit or two digits.
- Hint 2
A single digit decode is valid if the digit is 1-9. A two-digit decode is valid if the two digits form a number between 10 and 26.
- Hint 3
dp[i] = number of ways to decode s[0..i-1]. If s[i-1] is valid single digit, add dp[i-1]. If s[i-2..i-1] is a valid two-digit number, add dp[i-2].
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.