LeetCode Solutions
class Solution {
public:
string crackSafe(int n, int k) {
string ans(n, '0');
dfs(pow(k, n), n, k, {ans}, ans);
return ans;
}
private:
bool dfs(int passwordSize, int n, int k, unordered_set<string>&& seen,
string& path) {
if (seen.size() == passwordSize)
return true;
string prefix = path.substr(path.length() - n + 1);
for (char c = '0'; c < '0' + k; ++c) {
prefix.push_back(c);
if (!seen.count(prefix)) {
seen.insert(prefix);
path.push_back(c);
if (dfs(passwordSize, n, k, move(seen), path))
return true;
path.pop_back();
seen.erase(prefix);
}
prefix.pop_back();
}
return false;
}
};
|
class Solution {
public String crackSafe(int n, int k) {
final String allZeros = "0".repeat(n);
StringBuilder sb = new StringBuilder(allZeros);
dfs((int) Math.pow(k, n), n, k, new HashSet<>(Arrays.asList(allZeros)), sb);
return sb.toString();
}
private boolean dfs(int passwordSize, int n, int k, Set<String> seen, StringBuilder path) {
if (seen.size() == passwordSize)
return true;
StringBuilder prefix = new StringBuilder(path.substring(path.length() - n + 1));
for (char c = '0'; c < '0' + k; ++c) {
prefix.append(c);
final String prefixStr = prefix.toString();
if (!seen.contains(prefixStr)) {
seen.add(prefixStr);
path.append(c);
if (dfs(passwordSize, n, k, seen, path))
return true;
path.deleteCharAt(path.length() - 1);
seen.remove(prefixStr);
}
prefix.deleteCharAt(prefix.length() - 1);
}
return false;
}
}
|
class Solution:
def crackSafe(self, n: int, k: int) -> str:
passwordSize = k**n
path = '0' * n
seen = set()
seen.add(path)
def dfs(path: str) -> str:
if len(seen) == passwordSize:
return path
for c in map(str, range(k)):
node = path[-n + 1:] + c if n > 1 else c
if node not in seen:
seen.add(node)
res = dfs(path + c)
if res:
return res
seen.remove(node)
return dfs(path)
|
