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

Problem Statement: Decode Ways

You are given a string s consisting of digits, where each digit represents a letter according to the following mapping:

1 -> 'A'
2 -> 'B'
...
26 -> 'Z'

Given a string s containing only digits, you need to determine how many ways you can decode it. The decoding rule can be applied multiple times.

Approach:

We can solve this problem using Dynamic Programming (DP). Let dp[i] represent the number of ways to decode the substring s[0...i-1]. Here’s the approach:

1. Base Case:
   • dp[0] = 1 (One way to decode an empty string).
   • If the first character of s is non-zero, initialize dp[1] = 1; otherwise, dp[1] = 0.
2. Recurrence Relation:
   • For each position i (starting from 2 to n):
     • If s[i-1] is a valid single digit (between ‘1’ and ‘9’), then dp[i] += dp[i-1].
     • If s[i-2:i] is a valid two-digit number (between ’10’ and ’26’), then dp[i] += dp[i-2].
3. Final Answer: The result will be 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.

Example:

For s = "226", the possible decodings are:

1. 2 2 6 -> “BBF”
2. 22 6 -> “VF”
3. 2 26 -> “BF”

Thus, the result is 3.

Code Implementation:

1. C:

#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] >= '1' && s[i-1] <= '9') dp[i] += dp[i-1];
        if (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) dp[i] += dp[i-2];
    }

    return dp[n];
}

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

2. C++:

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

int numDecodings(string s) {
    int n = s.size();
    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] >= '1' && s[i - 1] <= '9') dp[i] += dp[i - 1];
        if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) dp[i] += dp[i - 2];
    }

    return dp[n];
}

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

3. Java:

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) >= '1' && s.charAt(i - 1) <= '9') dp[i] += dp[i - 1];
            if (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')) dp[i] += dp[i - 2];
        }

        return dp[n];
    }

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

4. Python:

def numDecodings(s: str) -> int:
    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):
        dp[i] = 0
        if '1' <= s[i - 1] <= '9':
            dp[i] += dp[i - 1]
        if s[i - 2] == '1' or (s[i - 2] == '2' and '0' <= s[i - 1] <= '6'):
            dp[i] += dp[i - 2]

    return dp[n]

# Example usage:
print(numDecodings("226"))

5. C#:

using System;

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] >= '1' && s[i - 1] <= '9') dp[i] += dp[i - 1];
            if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) dp[i] += dp[i - 2];
        }

        return dp[n];
    }

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

6. JavaScript:

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

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

    for (let i = 2; i <= n; i++) {
        dp[i] = 0;
        if (s[i - 1] >= '1' && s[i - 1] <= '9') dp[i] += dp[i - 1];
        if (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6')) dp[i] += dp[i - 2];
    }

    return dp[n];
}

console.log(numDecodings("226"));

Summary:

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

The solution is efficient and works for strings of moderate length, typically up to 10^3 or 10^4 digits.