Decode Ways

MediumDynamic ProgrammingDynamic Programming

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A message containing letters from A-Z can be encoded into numbers using the mapping: 'A' → "1", 'B' → "2", ..., 'Z' → "26". To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. Given a string s containing only digits, return the number of ways to decode it.

Examples

Input: s = "12"
Output: 2
"12" could be decoded as "AB" (1 2) or "L" (12).
Input: s = "226"
Output: 3
"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Input: s = "06"
Output: 0
"06" cannot be mapped to "F" because of the leading zero.

Constraints

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zeros.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More Dynamic Programming problems