Count ways to decode digit string

Q: Count ways to decode digit string

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Count ways to decode digit string

Overview

Comments (0)