753

753. Cracking the Safe (Hard)

There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].

The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.

• For example, the correct password is "345" and you enter in "012345":

  <ul>
  	<li>After typing <code>0</code>, the most recent <code>3</code> digits is <code>"0"</code>, which is incorrect.</li>
  	<li>After typing <code>1</code>, the most recent <code>3</code> digits is <code>"01"</code>, which is incorrect.</li>
  	<li>After typing <code>2</code>, the most recent <code>3</code> digits is <code>"012"</code>, which is incorrect.</li>
  	<li>After typing <code>3</code>, the most recent <code>3</code> digits is <code>"123"</code>, which is incorrect.</li>
  	<li>After typing <code>4</code>, the most recent <code>3</code> digits is <code>"234"</code>, which is incorrect.</li>
  	<li>After typing <code>5</code>, the most recent <code>3</code> digits is <code>"345"</code>, which is correct and the safe unlocks.</li>
  </ul>
  </li>
  

Return any string of minimum length that will unlock the safe at some point of entering it.

 

Example 1:

Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.

Example 2:

Input: n = 2, k = 2
Output: "01100"
Explanation: For each possible password:
- "00" is typed in starting from the 4th digit.
- "01" is typed in starting from the 1st digit.
- "10" is typed in starting from the 3rd digit.
- "11" is typed in starting from the 2nd digit.
Thus "01100" will unlock the safe. "01100", "10011", and "11001" would also unlock the safe.

 

Constraints:

• 1 <= n <= 4
• 1 <= k <= 10
• 1 <= kn <= 4096

Companies:
Google, Apple

Related Topics:
Depth-First Search, Graph, Eulerian Circuit

Solution 1. DFS

Given n and k, there will be k^n unique passwords. When I was solving this problem, I had an assumption that

• the best answer should have each of those passwords appear exactly once
• each password should exactly use the last n-1 digits of its previous password.

This assumption can be proved by De Bruijn sequence.

So the answer should be of length n + k^n - 1.

We can use DFS to try all digits at each level and backtrack if the new digit can't form a new password. Once we've visited k^n unique passwords, we know that we've found the answer.

// OJ: https://leetcode.com/problems/cracking-the-safe/
// Author: github.com/lzl124631x
// Time: O((NK)^(K^N))
// Space: O(N*(K^N))
class Solution {
private:
public:
    string crackSafe(int n, int k) {
        string ans(n, '0');
        unordered_set<string> seen{{ans}};
        int goal = pow(k, n);
        function<bool()> dfs = [&]() {
            if (seen.size() == goal) return true;
            for (int i = 0; i < k; ++i) {
                ans += '0' + i;
                auto pwd = ans.substr(ans.size() - n);
                if (!seen.count(pwd)) {
                    seen.insert(pwd);
                    if (dfs()) return true;
                    seen.erase(pwd);
                }
                ans.pop_back();
            }
            return false;
        };
        dfs();
        return ans;
    }
};

Solution 2. DFS (post-order Hierholzer's algorithm)

We can think of this problem as a problem of finding an Eulerian path (a path visiting every edge exactly once) on the following graph: there are k^(n − 1) nodes with each node standing for n - 1 digits and having k edges

For example, when k = 4, n = 3, the nodes are '00', '01', '02', ..., '32', '33' and each node has 4 edges '0', '1', '2', '3'. A node plus edge represents a complete edge which forms a password and is a substring of our answer.

Any connected directed graph where all nodes have equal in-degree and out-degree has an Eulerian circuit (an Eulerian path ending where it started.) Because our graph is highly connected and symmetric, we should expect intuitively that taking any path greedily in some order will probably result in an Eulerian path.

This intuition is called Hierholzer's algorithm: whenever there is an Eulerian circuit, we can construct it greedily. Please see my note of this algorithm here.

Note that we shouldn't add the edge into the answer right after we visit it, because it will cause us to get stuck prematurely. For example, with k = 2, n = 2, we have the nodes '0', '1'. If we greedily visit complete edges '00', '01', '10', we will be stuck at the node '0' prematurely. So we should record the edges in post-order, that is, after finding a complete Eulerian circuit, keep recording the edges into answer as we back-tracking to the start node.

Again, take the k = 2, n = 2 as example, we visit the complete edges in the following order:

 a     0     b     1     c     0     d
(0) ------> (0) ------> (1) ------> (0) [Stuck! Backtrack]
      [00]        [01]   |    [10]
                         |
                         |     1      e
                         └---------> (1) [All passwords visited!]
                              [11]

We output d -> e -> c -> b i.e. 0110 to the ans string. Since start = "0", the answer is ans + start = "01100".

// OJ: https://leetcode.com/problems/cracking-the-safe/
// Author: github.com/lzl124631x
// Time: O(N^(K^N))
// Space: O(N*(K^N))
class Solution {
public:
    string crackSafe(int n, int k) {
        if (n == 1 && k == 1) return "0";
        unordered_set<string> seen;
        string ans, start(n - 1, '0');
        function<void(string)> euler = [&](string u) {
            for (char c = '0'; c < '0' + k; ++c) {
                auto v = u + c;
                if (seen.count(v)) continue;
                seen.insert(v);
                euler(v.substr(1));
                ans.push_back(c);
            }
        };
        euler(start);
        return ans + start;
    }
};