Decode Ways In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of HTML code highlighted in vibrant colors on a computer monitor.

Problem Statement: Decode Ways

Given a string s consisting of digits, return the total number of ways to decode it.

A digit from 1 to 26 represents a letter from A to Z (i.e., ‘1’ -> ‘A’, ‘2’ -> ‘B’, …, ’26’ -> ‘Z’).

For example:

  • s = "12" can be decoded as AB (1 2) or L (12). The total number of ways is 2.
  • s = "226" can be decoded as BBF (2 2 6), BZ (2 26), or VF (22 6). The total number of ways is 3.

Note:

  1. A leading zero is not valid.
  2. The input string is non-empty and consists of digits.

Example 1:

Input:

s = "12"

Output:

2

Explanation: The possible decodings are:

  • “AB” (1 2)
  • “L” (12)

Example 2:

Input:

s = "226"

Output:

3

Explanation: The possible decodings are:

  • “BBF” (2 2 6)
  • “BZ” (2 26)
  • “VF” (22 6)

Approach

The problem can be solved using Dynamic Programming (DP). We will maintain a DP array where each entry dp[i] will represent the number of ways to decode the substring s[0..i-1].

Steps:

  1. Base Case:
    • dp[0] = 1: There’s one way to decode an empty string.
    • dp[1] = 1 if s[0] != '0', otherwise dp[1] = 0 because a string starting with ‘0’ is not valid.
  2. Recursive Case:
    • For each position i from 2 to n (length of the string):
      • If s[i-1] is a valid single digit (i.e., s[i-1] != '0'), then dp[i] += dp[i-1] (i.e., the number of ways to decode up to the previous character).
      • If the two characters s[i-2] and s[i-1] form a valid two-digit number (i.e., 10 <= s[i-2..i-1] <= 26), then dp[i] += dp[i-2].
  3. Final Answer: The value at dp[n] (where n is the length of the string) will give the total number of ways to decode the entire string.

Time Complexity:

  • Time Complexity: O(n), where n is the length of the string. We are iterating through the string once and performing constant-time checks and updates for each character.
  • Space Complexity: O(n), for storing the DP array.

Code Implementations

C Implementation

#include <stdio.h>
#include <string.h>

int numDecodings(char* s) {
    int n = strlen(s);
    if (n == 0 || s[0] == '0') return 0;
    
    int dp[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = 0;
        if (s[i - 1] != '0') dp[i] += dp[i - 1]; // Single digit
        if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) {
            dp[i] += dp[i - 2]; // Two digits (10 to 26)
        }
    }
    return dp[n];
}

int main() {
    char s[] = "226";
    printf("Number of decodings: %d\n", numDecodings(s));
    return 0;
}

C++ Implementation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int numDecodings(string s) {
    int n = s.size();
    if (n == 0 || s[0] == '0') return 0;

    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1]; // Single digit
        if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) {
            dp[i] += dp[i - 2]; // Two digits (10 to 26)
        }
    }
    return dp[n];
}

int main() {
    string s = "226";
    cout << "Number of decodings: " << numDecodings(s) << endl;
    return 0;
}

Java Implementation

public class DecodeWays {
    public static int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') return 0;

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

        for (int i = 2; i <= n; i++) {
            dp[i] = 0;
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1]; // Single digit
            if (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')) {
                dp[i] += dp[i - 2]; // Two digits (10 to 26)
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        String s = "226";
        System.out.println("Number of decodings: " + numDecodings(s));
    }
}

Python Implementation

pythonCopy codedef numDecodings(s):
    n = len(s)
    if n == 0 or s[0] == '0': return 0

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]  # Single digit
        if s[i - 2] == '1' or (s[i - 2] == '2' and s[i - 1] <= '6'):
            dp[i] += dp[i - 2]  # Two digits (10 to 26)

    return dp[n]

# Example usage
s = "226"
print("Number of decodings:", numDecodings(s))

C# Implementation

using System;

public class DecodeWays
{
    public static int NumDecodings(string s)
    {
        int n = s.Length;
        if (n == 0 || s[0] == '0') return 0;

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

        for (int i = 2; i <= n; i++)
        {
            dp[i] = 0;
            if (s[i - 1] != '0') dp[i] += dp[i - 1]; // Single digit
            if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))
            {
                dp[i] += dp[i - 2]; // Two digits (10 to 26)
            }
        }
        return dp[n];
    }

    public static void Main()
    {
        string s = "226";
        Console.WriteLine("Number of decodings: " + NumDecodings(s));
    }
}

JavaScript Implementation

const numDecodings = (s) => {
    const n = s.length;
    if (n === 0 || s[0] === '0') return 0;

    const dp = Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        if (s[i - 1] !== '0') dp[i] += dp[i - 1]; // Single digit
        if (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6')) {
            dp[i] += dp[i - 2]; // Two digits (10 to 26)
        }
    }

    return dp[n];
};

// Example usage
const s = "226";
console.log("Number of decodings:", numDecodings(s));

Explanation:

  1. DP Array: The dp array keeps track of the number of ways to decode substrings of s. Each index i in dp represents the number of ways to decode the substring s[0..i-1].
  2. Base Case: dp[0] = 1 (empty string has 1 way to decode) and dp[1] = 1 if s[0] != '0'.
  3. Recursion: For each position i, we check:
    • If the current digit s[i-1] is a valid single digit (i.e., not ‘0’), we add dp[i-1] to dp[i].
    • If the last two digits form a valid number between 10 and 26, we add dp[i-2] to dp[i].
  4. Final Result: The result is stored in dp[n] where n is the length of the string.

Time Complexity:

  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(n), for the dp array.