Skip to content

Decode Ways II⚓︎

Link

Description⚓︎

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

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

  • "AAJF" with the grouping (1 1 10 6)
  • "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

In addition to the mapping above, an encoded message may contain the '*' character, which can represent any digit from '1' to '9' ('0' is excluded). For example, the encoded message "1*" may represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Decoding "1*" is equivalent to decoding any of the encoded messages it can represent.

Given a string s consisting of digits and '*' characters, return the number of ways to decode it.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

  • Input: s = "*"
  • Output: 9
  • Explanation:
1
2
3
The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9".
Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively.
Hence, there are a total of 9 ways to decode "*".

Example 2:

  • Input: s = "1*"
  • Output: 18
  • Explanation:
1
2
3
The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K").
Hence, there are a total of 9 * 2 = 18 ways to decode "1*".

Example 3:

  • Input: s = "2*"
  • Output: 15
  • Explanation:
1
2
3
The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".

Constraints:

  • 1 <= s.length <= 10^5
  • s[i] is a digit or '*'.

Solution⚓︎

Top-Down⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
private:
    const static long long mod = 1e9 + 7;

    long long calculate(vector<long long>& dp, const string& s, int start) {
        if (start == s.length()) {
            return 1;
        }

        if (s[start] == '0') {
            return 0;
        }

        if (dp[start] != -1) {
            return dp[start];
        }

        long long res = calculate(dp, s, start + 1) * (s[start] == '*' ? 9 : 1);

        if (start + 1 < s.length()) {
            if (s[start] != '*') {
                if (s[start + 1] != '*') {
                    if (stoi(s.substr(start, 2)) <= 26) {
                        res += calculate(dp, s, start + 2);
                    }
                } else {  // s[start + 1] == '*'
                    if (s[start] == '1') {
                        res += calculate(dp, s, start + 2) * 9;
                    } else if (s[start] == '2') {
                        res += calculate(dp, s, start + 2) * 6;
                    }
                }
            } else {  // s[start] == '*'
                if (s[start + 1] != '*') {
                    if (s[start + 1] <= '6') {
                        res += calculate(dp, s, start + 2) * 2;
                    } else {
                        res += calculate(dp, s, start + 2);
                    }
                } else {  // s[start + 1] == '*'
                    res += calculate(dp, s, start + 2) * 15;
                }
            }
        }

        res %= mod;
        dp[start] = res;

        return res;
    }

public:
    int numDecodings(string s) {
        vector<long long> dp(s.length(), -1);
        return static_cast<int>(calculate(dp, s, 0));
    }
};

Bottom-Up⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
private:
    const static long long mod = 1e9 + 7;
public:
    int numDecodings(string s) {
        int n = s.length();
        vector<long long> dp(n + 1);
        dp[n] = 1;

        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') continue;
            dp[i] = dp[i + 1] * (s[i] == '*' ? 9 : 1);

            if (i + 1 >= n) continue;
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    if (stoi(s.substr(i, 2)) <= 26) dp[i] += dp[i + 2];
                } else {
                    if (s[i] == '1') dp[i] += dp[i + 2] * 9;
                    else if (s[i] == '2') dp[i] += dp[i + 2] * 6;
                }
            } else {
                if (s[i + 1] != '*') {
                    if (s[i + 1] <= '6') dp[i] += dp[i + 2] * 2;
                    else dp[i] += dp[i + 2];
                } else dp[i] += dp[i + 2] * 15;
            }

            dp[i] %= mod;
        }

        return static_cast<int>(dp[0]);
    }
};

Initial Setup:

  • DP Array Initialization: dp[n] = 1; This base case facilitates the computation of dp[i] for i < n by providing a starting point indicating that there is exactly one way to decode an empty string.

Single-Character Decoding:

When decoding a single character, there are two cases to consider:

  1. The character is a digit (1-9): Each of these characters can only be decoded in one way (e.g., '1' -> 'A', '2' -> 'B', etc.).
  2. The character is a wildcard (*): The '*' can represent any digit from '1' to '9', so there are 9 ways to decode it.

The code dp[i] = dp[i + 1] * (s[i] == '*' ? 9 : 1); calculates the number of ways to decode the string starting from position i considering only the single-character decoding at position i. It multiplies the number of ways to decode the substring starting from i+1 by 9 if the current character is '*', or by 1 if it's any digit from 1 to 9.

Two-Character Decoding:

This is where the solution gets more nuanced, as it has to account for combinations of digits and '*', and how they can form valid two-digit numbers (10 to 26).

  1. Both characters are digits: The solution converts the two characters to an integer and checks if it's within the range 10 to 26. If so, this adds to the number of ways dp[i+2] can decode the rest of the string starting from position i+2.

  2. The first character is a digit and the second is '*':

  3. If the first character is '1', the '*' can represent any digit from '1' to '9', thus forming the numbers 11 to 19. Each of these is a valid encoding, so we add 9 * dp[i+2].

  4. If the first character is '2', the '*' can represent digits from '1' to '6' (forming the numbers 21 to 26), contributing 6 * dp[i+2] ways.

  5. The first character is '*' and the second is a digit:

  6. If the second digit is between '1' and '6', the first '*' can be '1' or '2', doubling the possibilities (2 * dp[i+2]).

  7. If the second digit is between '7' and '9', the '*' can only represent '1' to match the encoding rules, resulting in dp[i+2].

  8. Both characters are '*': This represents the most combinations, as '*' can be '1' or '2' forming valid two-digit numbers 11 to 19 and 21 to 26. There are 9 possibilities for the first '*', and for the second '*', there are 6 possibilities when the first '*' is '2'. Therefore, there are 9 + 6 = 15 total ways, resulting in 15 * dp[i+2].

Space-optimized approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private:
    const static long long mod = 1e9 + 7;
public:
    int numDecodings(string s) {
        int n = s.length();
        long long current = 0LL, nxt = 1LL, nxtNxt = 0LL;

        for (int i = n - 1; i >= 0; i--) {
            if (s[i] != '0') {
                current = nxt * (s[i] == '*' ? 9 : 1);

                if (i + 1 < n) {
                    if (s[i] != '*') {
                        if (s[i + 1] != '*') {
                            if (stoi(s.substr(i, 2)) <= 26) current += nxtNxt;
                        } else {
                            if (s[i] == '1') current += nxtNxt * 9;
                            else if (s[i] == '2') current += nxtNxt * 6;
                        }
                    } else {
                        if (s[i + 1] != '*') {
                            if (s[i + 1] <= '6') current += nxtNxt * 2;
                            else current += nxtNxt;
                        } else current += nxtNxt * 15;
                    }
                }

                current %= mod;
            }

            nxtNxt = nxt;
            nxt = current;
            current = 0;
        }

        return static_cast<int>(nxt);
    }
};