Katkat
Back

Count the Ways to Decode a Numeric Cipher

TeslaSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to solve a counting problem using dynamic programming by identifying overlapping subproblems in a sequence of numeric mappings.

Problem Statement

A message containing letters from 'A' to 'Z' is being encoded into numbers using the following mapping: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26.

Given a string s consisting of digits, return the total number of ways to decode it. Note that a single digit can be mapped to a letter, and a two-digit sequence can also be mapped if it falls between 10 and 26. Sequences like "06" are invalid because '0' does not map to a letter, and leading zeros are generally not permitted unless the number is '0' itself (which is not used here).

Function Signature

def count_decodings(s: str) -> int:

Constraints

  • 1 <= len(s) <= 100
  • s consists of digits '0' through '9'.

Examples

Example 1: Input: s = "12" Output: 2 Explanation: It can be decoded as "AB" (1, 2) or "L" (12).

Example 2: Input: s = "226" Output: 3 Explanation: It can be decoded as "BZ" (2, 26), "VF" (22, 6), or "BBF" (2, 2, 6).

Edge Cases

  • Strings starting with '0'.
  • Strings containing '0' in the middle (e.g., "101").
  • Strings with consecutive '0's (e.g., "100").

Hints

Hint 1

Think about how the number of ways to decode a string of length 'i' depends on the results for length 'i-1' and 'i-2'.

Hint 2

If the current character is '0', it cannot be decoded on its own, so it must be paired with the previous character.

Hint 3

A two-digit number is only a valid decoding if it is between 10 and 26 inclusive.

Follow-up questions

  • How would you optimize the space complexity of your solution to O(1)?
  • What changes would be required if the mapping included '0' -> 'A', '1' -> 'B', ..., '25' -> 'Z'?
  • How would you modify the function to return one possible decoded string instead of the total count?