Decode Ways medium

Problem Statement

A message containing letters from A-Z is being encoded to numbers using the following mapping:

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

Given a non-empty string containing only digits, determine the total number of ways to decode it.

The test cases are generated so that the answer fits in the range [1, 10⁵].

Example 1:

Input: s = "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Steps to Solve

The problem can be solved using dynamic programming. We can build a DP table where dp[i] represents the number of ways to decode the string up to index i.

1. Base Cases:

   • dp[0] = 1 (Empty string has one way to decode - itself)
   • dp[1] = 1 if s[0] is a valid character (1-9), otherwise 0.

2. Iteration: For each index i (starting from 2), we consider two possibilities:

   • Decode the current character alone: If s[i-1] is a digit from 1 to 9, then dp[i] += dp[i-1].
   • Decode the last two characters together: If s[i-2:i] (substring of length 2) represents a number from 10 to 26, then dp[i] += dp[i-2].

3. Result: dp[n] (where n is the length of the string) will hold the total number of ways to decode the entire string.

Explanation

The dynamic programming approach avoids redundant calculations. By storing the number of ways to decode substrings, we can efficiently compute the result for the entire string. The base cases handle the trivial scenarios of empty or single-character strings. The iterative step carefully checks the validity of single and two-character decodings to ensure accuracy.

Code

#include <string>
#include <vector>

using namespace std;

int numDecodings(string s) {
    int n = s.length();
    if (n == 0) return 0; // Handle empty string case

    vector<int> dp(n + 1, 0);
    dp[0] = 1; // Base case: empty string has one decoding

    if (s[0] != '0') { //Base case: Single digit
        dp[1] = 1;
    }

    for (int i = 2; i <= n; i++) {
        int oneDigit = s[i - 1] - '0';
        int twoDigits = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');


        if (oneDigit >= 1 && oneDigit <= 9) {
            dp[i] += dp[i - 1];
        }
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
• Space Complexity: O(n), due to the dp vector used for dynamic programming. This can be optimized to O(1) by only storing the last two DP values.