Design Gurus Logo
Blind 75

Problem Statement

You have given a string that consists only of digits. This string can be decoded into a set of alphabets where '1' can be represented as 'A', '2' as 'B', ... , '26' as 'Z'. The task is to determine how many ways the given digit string can be decoded into alphabets.

Examples

    • Input: "121"
    • Expected Output: 3
    • Justification: The string "121" can be decoded as "ABA", "AU", and "LA".
    • Input: "27"
    • Expected Output: 1
    • Justification: The string "27" can only be decoded as "BG".
    • Input: "110"
    • Expected Output: 1
    • Justification: The string "110" can only be decoded as "AJ".

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

Solution

Our approach to solving this problem involves using dynamic programming to iteratively build the solution. Given a string of digits, we want to determine how many ways it can be decoded into alphabets. The key insight is that the number of ways to decode a string of length i is dependent on the number of ways to decode the previous two substrings of length i-1 and i-2. We'll use two variables, prev and current, to store these values and update them as we loop through the string.

  1. Initialization: Begin by checking if the string is valid for decoding (e.g., it should not start with a '0'). If the string is invalid, return 0. Next, initialize two variables, prev and current, both set to 1. prev will store the number of ways to decode the string of length i-2, and current will store the number of ways to decode the string of length i-1.

  2. Iterate Through the String: Loop through the string from the second character to the end. For each character, compute the number of ways it can be decoded when combined with the previous character.

  3. Update Variables: For each character, evaluate the following conditions:

    • If the current character and the previous character form a valid number between 10 and 26, they can be decoded together.
    • If the current character is not '0', it can be decoded individually. Use these conditions to update the prev and current variables accordingly.

  4. Return the Result: Once the iteration completes, the current variable will hold the total number of ways the entire string can be decoded. Return this value.

This dynamic programming approach is efficient because it computes the solution by using previously calculated results, and it avoids redundant calculations. By tracking and updating the number of ways to decode the current and previous substrings, the algorithm effectively builds the solution for the entire string.

Algorithm Walkthrough

Let's trace the first example, "121". Move through the steps one at a time:

mediaLink

Step 1. The letters A to Z are the numbers 1 to 26, so reading the string means chopping it into pieces of one or two digits, each between 1 and 26. Every reading has to end somewhere, and it ends either by taking the last digit alone or by taking the last two together. That gives the rule for the row: each cell adds the cell before it, when the last digit can stand alone, and the cell two before it, when the last two digits form a number from 10 to 26. The first two cells are the starting facts.

1 of 5

Code

Python3
Python3

Complexity Analysis

  • Time Complexity: O(N), where N is the length of the string. We loop through the string once.

  • Space Complexity: O(1), as we only use a constant amount of space regardless of the input size.

No code editor for this lesson
This lesson focuses on concepts and theory