Katkat
Back

Count ways to decode digit string

SnapchatSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's skill in dynamic programming and combinatorial reasoning about string partitioning, testing competency in counting valid decodings under constraint handling and edge-case analysis.

You are given a string s consisting of digits '0' to '9'. The string encodes a message using the following mapping:

  • '1' → A, '2' → B, ..., '26' → Z.

A decoding is a way to partition s into one or more contiguous substrings, where each substring represents a valid number between 1 and 26 (inclusive), and then map each number to its corresponding letter.

Examples of valid decodings:

  • "12" can be decoded as "AB" (1 2) or "L" (12), so there are 2 ways.
  • "226" can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6), so there are 3 ways.

Rules:

  • A single '0' is not a valid code.
  • Any two-digit number must be between 10 and 26 inclusive.
  • Encodings like "06" or "30" are invalid because 0 cannot start a number, and 30 is not between 10 and 26.

Task

Given s, return the total number of different valid decodings.

Constraints

  • 1 <= len(s) <= 100
  • s consists only of characters '0'–'9'.

You may assume the result fits in a 32-bit signed integer.