1
\$\begingroup\$

I'm posting my C++ code for LeetCode's 1320. If you have time and would like to review, please do so. Thank you!

Problem

enter image description here

  • You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter \$A\$ is located at coordinate \$(0,0)\$, the letter \$B\$ is located at coordinate \$(0,1)\$, the letter \$P\$ is located at coordinate \$(2,3)\$ and the letter \$Z\$ is located at coordinate \$(4,1)\$.

  • Given the string word, return the minimum total distance to type such string using only two fingers. The distance between coordinates \$(x_1,y_1)\$ and \$(x_2,y_2)\$ is \$|x_1 - x_2| + |y_1 - y_2|\$.

  • Note that the initial positions of your two fingers are considered free so don't count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

Example 1:

Input: word = "CAKE" Output: 3

Explanation:

Using two fingers, one optimal way to type "CAKE" is:

  • Finger 1 on letter 'C' -> cost = 0
  • Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2
  • Finger 2 on letter 'K' -> cost = 0
  • Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1

Total distance = 3

Constraints:

  • \$2 \le \text{word.length} \le 300\$
  • Each word[i] is an English uppercase letter.

Accepted C++

#include <vector>
#include <string>
#include <algorithm>

class Solution {
    const unsigned short int ALPHABET_LEN = 26;
    const unsigned short int WIDTH = 6;
    const unsigned char A_LETTER = 'A';
public:

    std::size_t minimumDistance(const std::string word) {
        const std::size_t length = word.size();
        std::vector<int> dp(ALPHABET_LEN);
        int max_decrease = 0;
        int total_distance = 0;

        for (std::size_t index = 0; index < length - 1; index++) {
            const int second = word[index] - A_LETTER;
            const int third = word[index + 1] - A_LETTER;

            for (std::size_t first = 0; first < ALPHABET_LEN; first++) {
                dp[second] = std::max(dp[second], dp[first] + coordinates(second, third) - coordinates(first, third));
            }

            max_decrease = std::max(max_decrease, dp[second]);
            total_distance += coordinates(second, third);
        }

        return total_distance - max_decrease;
    }

private:
    unsigned short coordinates(unsigned short left, unsigned short right) {
        return std::abs(left / WIDTH - right / 6) + std::abs(left % WIDTH - right % WIDTH);
    }
};

Reference

On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice use of the default private region to declare your constants. \$\endgroup\$ – pacmaninbw Jun 23 at 22:45
3
\$\begingroup\$

Ensure you match the given API

Using size_t for sizes is a good thing to do, however the LeetCode problem specifies the API, and you should not change it. minimumDistance() should return int.

Use static constexpr for compile-time constants

Use static constexpr instead of const for the constants. This allows the compiler to make more optimizations, and they can then also be used in other places where a compile-time constant is required, for example:

Use a std::array

Since dp has a compile-time constant size, you can make it a std::array:

std::array<int, ALPHABET_LEN> dp;

Avoid using small types unnecessarily

Here you have a problem where you know the maximum distance between two letters is 25. I see you have decided to make coordinates() return an unsigned short. I would not do this. While it might seem more optimal, it is not: on many 32-bit and 64-bit platforms, 16-bit integers are often less efficient than 32-bit integers, since they are smaller than the natural register size, and thus the compiler might need to add instructions to ensure all but the lower 16 bits are zeroed. There might also be a penalty because it has to convert it back to a regular int when adding it the result to total_distance.

The right time to use shorts or even chars to hold integer values is when you have large arrays of them, since then it might reduce memory usage and memory bandwidth.

Proper naming

The function coordinates(), contrary to what the name implies, does not return coordinates. Instead, it returns a distance. So name it distance().

I would also not name the arguments left and right, but just a and b. Left and right sounds confusing here since you might think it gets the character under the left and right fingers as inputs.

Also, what does dp stand for? It seems like this vector holds the maximum distance traveled given a starting position. Try to find a more descriptive name for it. If there is no good one, then at least add a comment explaining what dp is.

The names second and third are slightly misleading for index > 0. Maybe it would be better to name them from and to.

Use WIDTH consistently

You still use one literal 6 in coordinates().

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ The new version looks fine! \$\endgroup\$ – G. Sliepen Jun 23 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.