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>"0"</code>, which is incorrect.</li> <li>After typing <code>1</code>, the most recent <code>3</code> digits is <code>"01"</code>, which is incorrect.</li> <li>After typing <code>2</code>, the most recent <code>3</code> digits is <code>"012"</code>, which is incorrect.</li> <li>After typing <code>3</code>, the most recent <code>3</code> digits is <code>"123"</code>, which is incorrect.</li> <li>After typing <code>4</code>, the most recent <code>3</code> digits is <code>"234"</code>, which is incorrect.</li> <li>After typing <code>5</code>, the most recent <code>3</code> digits is <code>"345"</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. "01100", "10011", and "11001" would also unlock the safe.
Constraints:
1 <= n <= 4
1 <= k <= 10
1 <= kn <= 4096
Solution(javascript)
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var crackSafe = function(n, k) {
let seen = new Set();
let ans = [];
const dfs = (node, k) => {
for (let x = 0; x < k; ++x) {
const nei = node + x;
if (!seen.has(nei)) {
seen.add(nei);
dfs(nei.slice(1), k);
ans.push(x);
}
}
};
if (n == 1 && k == 1) {
return "0";
}
seen = new Set();
ans = [];
const sb = [];
for (let i = 0; i < n-1; ++i) {
sb.push("0");
}
const start = sb.join('');
dfs(start, k);
ans.push(start);
return ans.join('');
};