Find the possible number of decodings of a given digit sequence | FACE Prep

Find the possible number of decodings of a given digit sequence | FACE Prep

Possible Decodings of a Digit Sequence | Efficient Approach

Introduction

Decoding a digit sequence into meaningful characters is a common problem in coding interviews and competitive programming. This article explores how to determine the number of possible decodings for a given sequence of digits.

Each digit from 1 to 26 corresponds to a letter in the alphabet:

  • ‘A’ represents 1
  • ‘B’ represents 2
  • ‘Z’ represents 26

Example

Input:

digits[] = "123"

Output:

3

Possible Decodings:

  • “ABC” (1 2 3)
  • “LC” (12 3)
  • “AW” (1 23)

Input:

digits[] = "121"

Output:

3

Possible Decodings:

  • “ABA” (1 2 1)
  • “AU” (1 21)
  • “LA” (12 1)

Algorithm to Find the Number of Decodings

  1. Read the digit sequence.
  2. Initialize count = 0.
  3. If the last digit is non-zero, recursively check for the next remaining (n-1) digits and add the result to the total count.
  4. If the last two digits form a valid character (≤26), recursively check for the remaining (n-2) digits and add the result to the total count.
  5. Continue until the entire sequence is processed.

Program to Find the Possible Number of Decodings

Method 1: Recursion

#include <iostream>
using namespace std;

int countDecodings(string digits, int n) {
    if (n == 0 || n == 1) return 1;
    if (digits[0] == '0') return 0;

    int count = 0;
    if (digits[n - 1] > '0')
        count = countDecodings(digits, n - 1);

    if (digits[n - 2] == '1' || (digits[n - 2] == '2' && digits[n - 1] < '7'))
        count += countDecodings(digits, n - 2);

    return count;
}

int main() {
    string digits = "121";
    cout << "Total Decodings: " << countDecodings(digits, digits.size());
    return 0;
}

Method 2: Dynamic Programming

class DecodeWays {
    static int countDecodings(String digits) {
        int n = digits.length();
        if (n == 0 || digits.charAt(0) == '0') return 0;

        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (digits.charAt(i - 1) > '0')
                dp[i] = dp[i - 1];

            int twoDigit = Integer.parseInt(digits.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        String digits = "123";
        System.out.println("Total Decodings: " + countDecodings(digits));
    }
}

Complexity Analysis

  • Recursive Approach: Exponential O(2^n) (can be optimized using memoization)
  • Dynamic Programming Approach: O(n) (better efficiency)

Suggested Visuals

  • Flowchart: To illustrate the recursive breakdown of decoding.
  • Table Representation: Showing DP states for different inputs.
  • Tree Diagram: Depicting possible decoding paths.

Conclusion

Understanding how to count decodings of a digit sequence is essential for mastering dynamic programming and recursion. The recursive approach provides an intuitive understanding, while dynamic programming ensures efficiency. By implementing these methods, you can solve similar problems related to string decoding and encoding.

Recommended Programs

  • Convert digit/number to words
  • Find the number of times digit 3 occurs in numbers from 0 to n
  • Count integers with exactly 9 divisors
  • Solve permutations where n people occupy r seats in a theater
  • Roots of a quadratic equation
Possible Decodings of a Digit Sequence | Efficient Approach

c