[LeetCode] 753. Cracking the Safe 破解密码

2021年09月15日 阅读数：1

You can keep inputting the password, the password will automatically be matched against the last `n` digits entered.html

For example, assuming the password is `"345"`, I can open it when I type `"012345"`, but I enter a total of 6 digits.java

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.node

Example 1:python

```Input: n = 1, k = 2
Output: "01"
Note: "10" will be accepted too.```

Example 2:c++

```Input: n = 2, k = 2
Output: "00110"
Note: "01100", "10011", "11001" will be accepted too. ```

Note:git

1. `n` will be in the range `[1, 4]`.
2. `k` will be in the range `[1, 10]`.
3. `k^n` will be at most `4096`.

Hint:app

We can think of this problem as the problem of finding an Euler path (a path visiting every edge exactly once) on the following graph: there are \$\$k^{n-1}\$\$ nodes with each node having \$\$k\$\$ edges. It turns out this graph always has an Eulerian circuit (path starting where it ends.) We should visit each node in "post-order" so as to not get stuck in the graph prematurely.post

goal: to find the minimum String that matches all combinations of 1..k with length n.
to build the graph:
node: all possible combinations, e.g. 00, 01, 11, 10;
edge: if the last n - 1 digits of node1 can be transformed to node2 by appending a digit from 1..k, e.g. 01 => (1 + 1) => 11, there will be an edge between node1 and node2 ;
transition:
For each node, we pick its last n - 1 digits. if the digits picked can be transfromed to a valid combination, i.e., another node which has not been visited by appending one more digit from 1..k, we go further following the same pattern... we stop when we have visited all the possible combinations, i.e., all nodes.
start node: 0...0 (n 0's) e.g. 00 for n = 2;
end: when visited.size() == k^n;

Java:

```class Solution {
public String crackSafe(int n, int k) {
StringBuilder sb = new StringBuilder();
int total = (int) (Math.pow(k, n));
for (int i = 0; i < n; i++) sb.append('0');

Set<String> visited = new HashSet<>();

dfs(sb, total, visited, n, k);

return sb.toString();
}

private boolean dfs(StringBuilder sb, int goal, Set<String> visited, int n, int k) {
if (visited.size() == goal) return true;
String prev = sb.substring(sb.length() - n + 1, sb.length());
for (int i = 0; i < k; i++) {
String next = prev + i;
if (!visited.contains(next)) {
sb.append(i);
if (dfs(sb, goal, visited, n, k)) return true;
else {
visited.remove(next);
sb.delete(sb.length() - 1, sb.length());
}
}
}
return false;
}

}
```

Java:

``` public String crackSafe(int n, int k) {

StringBuilder result = new StringBuilder();
for (int i = 0; i < n; i++) {
result.append("0");
}
Set<String> visited = new HashSet<>();
crackSafeFrom(result, n, k, (int) Math.pow(k, n), visited);

return result.toString();
}

private boolean crackSafeFrom(StringBuilder result, int n, int k, int total, Set<String> visited) {

if (visited.size() == total) {
return true;
}

String curNode = result.substring(result.length() - n + 1);

for (char c = '0'; c < '0' + k; c++) {
if (!visited.contains(curNode + c)) {
result.append(c);
if (crackSafeFrom(result, n, k, total, visited)) {
return true;
}
result.deleteCharAt(result.length() - 1);
visited.remove(curNode + c);
}
}
return false;
}　　```

Python:

```# Time:  O(n * k^n)
# Space: O(n * k^n)
class Solution(object):
def crackSafe(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
def dfs(k, node, lookup, result):
for i in xrange(k):
neighbor = node + str(i)
if neighbor not in lookup:
result.append(str(i))
dfs(k, neighbor[1:], lookup, result)
break

result = [str(k-1)]*(n-1)
lookup = set()
dfs(k, "".join(result), lookup, result)
return "".join(result)
```

Python:

```# Time:  O(n * k^n)
# Space: O(n * k^n)
class Solution(object):
def crackSafe(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
result = [str(k-1)]*n
lookup = {"".join(result)}
total = k**n
while len(lookup) < total:
node = result[len(result)-n+1:]
for i in xrange(k):
neighbor = "".join(node) + str(i)
if neighbor not in lookup:
result.append(str(i))
break
return "".join(result)
```

Python:

```# Time:  O(k^n)
# Space: O(k^n)
class Solution(object):
def crackSafe(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
M = k**(n-1)
P = [q*k+i for i in xrange(k) for q in xrange(M)]  # rotate: i*k^(n-1) + q => q*k + i
result = [str(k-1)]*(n-1)
for i in xrange(k**n):
j = i
# concatenation in lexicographic order of Lyndon words
while P[j] >= 0:
result.append(str(j//M))
P[j], j = -1, P[j]
return "".join(result)
```

C++:

```class Solution {
public:
string crackSafe(int n, int k) {
string res = string(n, '0');
unordered_set<string> visited{{res}};
helper(n, k, pow(k, n), visited, res);
return res;
}
void helper(int n, int k, int total, unordered_set<string>& visited, string& res) {
if (visited.size() == total) return;
string pre = res.substr(res.size() - n + 1, n - 1);
for (int i = k - 1; i >= 0; --i) {
string cur = pre + to_string(i);
if (visited.count(cur)) continue;
visited.insert(cur);
res += to_string(i);
helper(n, k, total, visited, res);
}
}
};
```

C++:

```class Solution {
public:
string crackSafe(int n, int k) {
string res = string(n, '0');
unordered_set<string> visited{{res}};
for (int i = 0; i < n * k; ++i) {
string pre = res.substr(res.size() - n + 1, n - 1);
for (int j = k - 1; j >= 0; --j) {
string cur = pre + to_string(j);
if (!visited.count(cur)) {
visited.insert(cur);
res += to_string(j);
break;
}
}
}
return res;
}
};
```