LeetCode 0753. Cracking the Safe Solution in Java, C++, Python & More | Explanation + Code

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":

  <ul>
  	<li>After typing <code>0</code>, the most recent <code>3</code> digits is <code>&quot;0&quot;</code>, which is incorrect.</li>
  	<li>After typing <code>1</code>, the most recent <code>3</code> digits is <code>&quot;01&quot;</code>, which is incorrect.</li>
  	<li>After typing <code>2</code>, the most recent <code>3</code> digits is <code>&quot;012&quot;</code>, which is incorrect.</li>
  	<li>After typing <code>3</code>, the most recent <code>3</code> digits is <code>&quot;123&quot;</code>, which is incorrect.</li>
  	<li>After typing <code>4</code>, the most recent <code>3</code> digits is <code>&quot;234&quot;</code>, which is incorrect.</li>
  	<li>After typing <code>5</code>, the most recent <code>3</code> digits is <code>&quot;345&quot;</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. "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).

PythonJavaC++GoTypeScript

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)(code-box)

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); } } } }(code-box)

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; } };(code-box)

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() }(code-box)

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(''); }(code-box)