Decode Ways

XXX. Decode Ways

Dynamic Programming

String

Problem Statement:

Given a string s containing digits, determine the total number of ways to decode it. Each digit or pair of digits represents a letter (e.g., '1' -> 'A', '2' -> 'B', ..., '26' -> 'Z').

Algorithm:

1. Initialize a dp array of size n + 1, where n is the length of the input string.
2. Set dp[0] = 1 as the base case (an empty prefix has one decoding).
3. Iterate through the string from left to right:
   • If the current character is not '0', set dp[i] += dp[i-1].
   • If the current and previous characters form a valid two-digit number (≤ 26), set dp[i] += dp[i-2].
4. Return dp[n] as the total number of ways to decode the entire string.

Complexity:

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

Java Implementation:

public int numDecodings(String s) {
    if (s.length() == 0) return 0;

    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1; // Base case: one way to decode an empty string

    // Iterate through the string
    for (int i = 1; i <= n; i++) {
        // Check single digit
        if (s.charAt(i - 1) != '0')
            dp[i] += dp[i - 1];

        // Check two digits
        if (i > 1) {
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigits >= 10 && twoDigits <= 26)
                dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}
                

Python Implementation:

def numDecodings(s):
    if not s:
        return 0

    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case: one way to decode an empty string

    # Iterate through the string
    for i in range(1, n + 1):
        # Check single digit
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]

        # Check two digits
        if i > 1:
            two_digits = int(s[i - 2:i])
            if 10 <= two_digits <= 26:
                dp[i] += dp[i - 2]

    return dp[n]
                

C++ Implementation:

int numDecodings(string s) {
    if (s.empty()) return 0;

    int n = s.length();
    vector dp(n + 1, 0);
    dp[0] = 1; // Base case: one way to decode an empty string

    // Iterate through the string
    for (int i = 1; i <= n; i++) {
        // Check single digit
        if (s[i - 1] != '0')
            dp[i] += dp[i - 1];

        // Check two digits
        if (i > 1) {
            int two_digits = stoi(s.substr(i - 2, 2));
            if (two_digits >= 10 && two_digits <= 26)
                dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}