LeetCode 753: Cracking the Safe

Question

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

Problem

• There is a box protected by a password. The password is a sequence of n digits where each digit can be one of the first k digits 0, 1, ..., k-1.

• While entering a password, the last n digits entered will automatically be matched against the correct password.

• For example, assuming the correct password is "345", if you type "012345", the box will open because the correct password matches the suffix of the entered password.

• Return any password of minimum length that is guaranteed to open the box at some point of entering it.

Accepted Code

#include <vector>
#include <string>
class Solution {
 int n;
 int k;
 int value;
 std::vector<std::vector<bool>> visited;
 std::string base_sequence;
public:
 std::string crackSafe(int n, int k) {
 if (k == 1) {
 return std::string(n, '0');
 }
 this->n = n;
 this->k = k;
 value = 1;
 for (int index = 0; index < n - 1; index++) {
 value *= k;
 }
 visited.resize(value, std::vector<bool>(k, false));
 depth_first_search(0);
 return base_sequence + base_sequence.substr(0, n - 1);
 }
private:
 // Depth first search the neighbor value
 void depth_first_search(int neighbor) {
 for (int index = 0; index < k; index++) {
 if (!visited[neighbor][index]) {
 visited[neighbor][index] = true;
 depth_first_search((neighbor * k + index) % value);
 base_sequence.push_back('0' + index);
 }
 }
 }
};

Reference

LeetCode has a template for answering questions. There is usually a class named Solution with one or more public functions which we are not allowed to rename.

• Problem

• Discuss

• Bellman Ford algorithm

Answer 1

Constant members

n and k can be constant, so long as

• you remove them from being parameters to crackSafe
• you add them as parameters to a constructor
• the constructor uses inline initialization syntax, i.e. n(n)

Basically, your two member functions should - in their current form - be bare functions outside of a class, since the class member variables only really have transient meaning. For this to make sense as a class, n and k would only make sense as "permanent" attributes per instance.