Skip to content

753. Cracking the Safe

Description

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":
    • After typing 0, the most recent 3 digits is "0", which is incorrect.
    • After typing 1, the most recent 3 digits is "01", which is incorrect.
    • After typing 2, the most recent 3 digits is "012", which is incorrect.
    • After typing 3, the most recent 3 digits is "123", which is incorrect.
    • After typing 4, the most recent 3 digits is "234", which is incorrect.
    • After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.

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. "10011", and "11001" would also unlock the safe.

 

Constraints:

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

Solutions

Solution 1: Eulerian Circuit

We can construct a directed graph based on the description in the problem: each point is considered as a length \(n-1\) \(k\)-string, and each edge carries a character from \(0\) to \(k-1\). If there is a directed edge \(e\) from point \(u\) to point \(v\), and the character carried by \(e\) is \(c\), then the last \(k-1\) characters of \(u+c\) form the string \(v\). At this point, the edge \(u+c\) represents a password of length \(n\).

In this directed graph, there are \(k^{n-1}\) points, each point has \(k\) outgoing edges and \(k\) incoming edges. Therefore, this directed graph has an Eulerian circuit, and the path traversed by the Eulerian circuit is the answer to the problem.

The time complexity is \(O(k^n)\), and the space complexity is \(O(k^n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        def dfs(u):
            for x in range(k):
                e = u * 10 + x
                if e not in vis:
                    vis.add(e)
                    v = e % mod
                    dfs(v)
                    ans.append(str(x))

        mod = 10 ** (n - 1)
        vis = set()
        ans = []
        dfs(0)
        ans.append("0" * (n - 1))
        return "".join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    private Set<Integer> vis = new HashSet<>();
    private StringBuilder ans = new StringBuilder();
    private int mod;

    public String crackSafe(int n, int k) {
        mod = (int) Math.pow(10, n - 1);
        dfs(0, k);
        ans.append("0".repeat(n - 1));
        return ans.toString();
    }

    private void dfs(int u, int k) {
        for (int x = 0; x < k; ++x) {
            int e = u * 10 + x;
            if (vis.add(e)) {
                int v = e % mod;
                dfs(v, k);
                ans.append(x);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string crackSafe(int n, int k) {
        unordered_set<int> vis;
        int mod = pow(10, n - 1);
        string ans;
        function<void(int)> dfs = [&](int u) {
            for (int x = 0; x < k; ++x) {
                int e = u * 10 + x;
                if (!vis.count(e)) {
                    vis.insert(e);
                    dfs(e % mod);
                    ans += (x + '0');
                }
            }
        };
        dfs(0);
        ans += string(n - 1, '0');
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func crackSafe(n int, k int) string {
    mod := int(math.Pow(10, float64(n-1)))
    vis := map[int]bool{}
    ans := &strings.Builder{}
    var dfs func(int)
    dfs = func(u int) {
        for x := 0; x < k; x++ {
            e := u*10 + x
            if !vis[e] {
                vis[e] = true
                v := e % mod
                dfs(v)
                ans.WriteByte(byte('0' + x))
            }
        }
    }
    dfs(0)
    ans.WriteString(strings.Repeat("0", n-1))
    return ans.String()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function crackSafe(n: number, k: number): string {
    function dfs(u: number): void {
        for (let x = 0; x < k; x++) {
            const e = u * 10 + x;
            if (!vis.has(e)) {
                vis.add(e);
                const v = e % mod;
                dfs(v);
                ans.push(x.toString());
            }
        }
    }

    const mod = Math.pow(10, n - 1);
    const vis = new Set<number>();
    const ans: string[] = [];

    dfs(0);
    ans.push('0'.repeat(n - 1));
    return ans.join('');
}

Comments