algoadvance

Leetcode 91. Decode Ways

Problem Statement

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be mapped back into letters using the reverse of the mapping above (some results may be invalid).

Given a string s containing only digits, return the number of ways to decode it.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with '0'. Hence, no valid decode ways.

Example 4:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero.

Clarifying Questions

  1. Input Constraints:
    • The string s will only contain digits and has a length between 1 and 100.
  2. Validity of the Input:
    • Can s contain invalid characters?
      • No, s will only contain digits.

Strategy

We can solve this problem using dynamic programming.

  1. Initialization:
    • Create a dp array where dp[i] will represent the number of ways to decode the substring s[0:i].
  2. Base Cases:
    • dp[0] = 1 (An empty string has one way to be decoded, which is not decoding at all).
    • If s[0] is not ‘0’, then dp[1] = 1; otherwise, dp[1] = 0.
  3. DP Transition:
    • For each character at position i:
      • If s[i] is not ‘0’, then dp[i] += dp[i-1] (Single character decode).
      • If the substring s[i-2:i] (i.e., two characters) is a valid decoding (between “10” to “26”), then dp[i] += dp[i-2].
  4. Final Answer:
    • The final answer will be dp[n] where n is the length of the string s.

Time Complexity

The time complexity for this solution is O(n), where n is the length of the string s. This is because we are iterating through the string once. The space complexity is also O(n) due to the dp array.

Code

#include <vector>
#include <string>

class Solution {
public:
    int numDecodings(std::string s) {
        if (s.empty() || s[0] == '0') return 0;

        int n = s.size();
        std::vector<int> dp(n + 1, 0);
        dp[0] = 1; // Base case: an empty string has one way to be decoded
        dp[1] = s[0] != '0' ? 1 : 0;

        for (int i = 2; i <= n; ++i) {
            int oneDigit = std::stoi(s.substr(i - 1, 1));
            int twoDigits = std::stoi(s.substr(i - 2, 2));
            
            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] += dp[i - 1];
            }
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
};

This code snippet effectively handles the problem requirements by utilizing dynamic programming to count the number of ways to decode the given string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI