LeetCode 639: Decode Ways II

Question

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

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

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

Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character '*', return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod \$10^9 + 7\$.

Example 1:

• Input: "*"
• Output: 9
• Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2:

• Input: "1*"
• Output: 9 + 9 = 18

Example 3:

• Input: "2*"
• Output: 15

Example 4:

• Input: "3*"
• Output: 9

Example 5:

• Input: "44*4"
• Output: 11

Note:

• The length of the input string will fit in range [1, 105].
• The input string will only contain the character '*' and digits '0' - '9'.

Code

#include <string>
#include <vector>

class Solution {
    static constexpr size_t MOD = 1e9 + 7;
public:
    static size_t numDecodings(const std::string message);
    static size_t decode(const char a_num_ast);
    static size_t decode(const char a_num_ast, const char b_num_ast);
};

inline size_t Solution::decode(const char a_num_ast) {
    if (a_num_ast == '*') {
        return 9;

    } else if (a_num_ast == '0') {
        return 0;

    } else {
        return 1;
    }
}

inline size_t Solution::decode(const char a_num_ast, const char b_num_ast) {
    if (a_num_ast == '1') {
        if (b_num_ast == '*') {
            return 9;

        } else if (b_num_ast >= '0' && b_num_ast <= '9') {
            return 1;
        }

    } else if (a_num_ast == '2') {
        if (b_num_ast == '*') {
            return 6;

        } else if (b_num_ast >= '0' && b_num_ast <= '6') {
            return 1;
        }

    } else if (a_num_ast == '0') {
        return 0;

    } else if (a_num_ast == '*') {
        return decode('1', b_num_ast) + decode('2',  b_num_ast);
    }

    return 0;
}

inline size_t Solution::numDecodings(const std::string message) {
    const size_t length = message.size();
    std::vector<size_t> decodes_dp(3, 0);
    decodes_dp[0] = 1;
    decodes_dp[1] = decode(message[0]);

    for (size_t index = 2; index <= length; index++) {
        decodes_dp[index % 3] = (decodes_dp[(index - 1) % 3] * decode(message[index - 1]) % MOD +
                                 decodes_dp[(index - 2) % 3] * decode(message[index - 2], message[index - 1]) % MOD) % MOD;
    }

    return decodes_dp[length % 3];
}

References

• Problem

• Solution

• Discuss

Answer 1

Make helper functions private

Member functions that are not part of the public API should be marked private. You should know that by now :)

Use uint64_t instead of size_t

There is no guarantee that size_t is big enough for the calculations you are doing. While you might only need 32 bits to store the results, you need to do the calculations using 64 bit integers (because you are multiplying two numbers that are each up to 30 bits in size). So to be safe, I would use uint64_t. You could use uint32_t as well, but then you need to explicitly cast to uint64_t before doing the multiplications inside numDecodings().

Use size_t for sizes and counts, but not for other purposes.

Make the decode() functions constexpr

I see you made MOD constexpr, which is great, but you can make the decode() functions constepxr as well.

Naming things

a_num_ast and b_num_ast are weird looking names. I'm guessing by a_num_ast you mean "a variable that can hold a number or an asterisk". But you shouldn't try to encode the type in the variable name. Just use a and b here.

What does decodes_dp mean? I would try to give it a better name. Use nouns for variables. Perhaps number_of_possibilities, or num_decodings (although that almost clashes with the function name).

Use std::array for fixed-length vectors

This avoids unnecessary heap allocations. So:

std::array<uint64_t, 3> decodes_dp{1, decode(message[0]), 0};

Remove unnecessary modulo operations

In the following expression:

decodes_dp[index % 3] = (
        decodes_dp[(index - 1) % 3] * decode(message[index - 1]) % MOD +
        decodes_dp[(index - 2) % 3] * decode(message[index - 2], message[index - 1]) % MOD
    ) % MOD;

Since you already need to use uint64_t for the result of the multiplications to not wrap, you don't need the modulo operations inside the outermost parentheses.

Consider using switch-statements

Your decode() functions can be rewritten as follows:

inline uint64_t Solution::decode(const char a) {
    switch(a) {
        case '0':
            return 0;
        case '*':
            return 9;
        default:
            return 1;
    }
}

inline uint64_t Solution::decode(const char a, const char b) {
    switch(a) {
        case '0':
            return 0;
        case '1':
            return b == '*' ? 9 : 1;
        case '2':
            switch(b) {
                case '0'...'6':
                    return 1;
                case '*':
                    return 6;
                default:
                    return 0;
            }
        case '*':
            return decode('1', b) + decode('2', b);
        default:
            return 0;
    }
}

It's more compact and avoids repeating a lot of if (a_num_ast ...), making it easier to see the structure of your code.