Cracking the Safe Solution in C++

Welcome to the world of “Cracking the Safe” where your coding skills are put to the ultimate test! Imagine you’re a master thief—no, not the kind who steals candy from a toddler, but the kind who cracks safes. You’re faced with a safe that uses a combination lock made up of numbers. Your task is to figure out the correct combination that opens the safe, and it’s no walk in the park!

Problem Description

You are given two integers n and k. Here, n represents the length of the password and k represents the number of different digits available (0 through k-1). Your goal? Construct a string that represents a combination of digits such that every possible combination of length n appears as a substring.

Code Solution


class Solution {
 public:
  string crackSafe(int n, int k) {
    string ans(n, '0');
    dfs(pow(k, n), n, k, {ans}, ans);
    return ans;
  }

 private:
  bool dfs(int passwordSize, int n, int k, unordered_set&& seen,
           string& path) {
    if (seen.size() == passwordSize)
      return true;

    string prefix = path.substr(path.length() - n + 1);

    for (char c = '0'; c < '0' + k; ++c) {
      prefix.push_back(c);
      if (!seen.contains(prefix)) {
        seen.insert(prefix);
        path.push_back(c);
        if (dfs(passwordSize, n, k, std::move(seen), path))
          return true;
        path.pop_back();
        seen.erase(prefix);
      }
      prefix.pop_back();
    }

    return false;
  }
};

Approach Explanation

The above code uses a depth-first search (DFS) strategy to explore every possible combination of digits. It constructs a string and checks if all possible combinations of length n have been seen. If not, it keeps adding digits until it finds a valid combination that meets the criteria.

Real-World Example

Imagine you're trying to unlock a super-secret vault filled with treasure! This vault doesn’t just accept any random number; it requires you to dial in every possible combination of four digits (0-3). With a little help from your coding skills and this algorithm, you'll crack the vault open faster than you can say "Jackpot!"

Time and Space Complexity

Time Complexity: O(kⁿ), where k is the number of digits and n is the length of the password.

Space Complexity: O(kⁿ), as well, due to the storage of all seen combinations in an unordered set.