Skip to content

Latest commit

 

History

History
220 lines (177 loc) · 6.4 KB

README_EN.md

File metadata and controls

220 lines (177 loc) · 6.4 KB
comments difficulty edit_url tags
true
Hard
Depth-First Search
Graph
Eulerian Circuit

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": 
    <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)$.

Python3

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)

Java

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);
            }
        }
    }
}

C++

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;
    }
};

Go

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

TypeScript

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