753. Cracking the Safe

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

  • After typing 0, the most recent 3 digits is "0", which is incorrect.

  • After typing 1, the most recent 3 digits is "01", which is incorrect.

  • After typing 2, the most recent 3 digits is "012", which is incorrect.

  • After typing 3, the most recent 3 digits is "123", which is incorrect.

  • After typing 4, the most recent 3 digits is "234", which is incorrect.

  • After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.

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

We know that the total combination count for the secret we want is n^k. The problem is asking the minimum length of trackCode to fulfill all combinations mention above. We observe that the best way to generate the trackCode is to reuse the last n-1 digit of the originalCrackCode.

Then we can write a backtracking solution for it.

long total = 0;
public String crackSafe(int n, int k) {
    StringBuilder sb = new StringBuilder();
    HashSet<String> visited = new HashSet<>();
    for(int i = 0; i < n; i++){
        sb.append("0");
    }
    total = (long)Math.pow(k, n);
    visited.add(sb.toString());
    dfs(sb, n, k, visited);
    return sb.toString();
}
//backTracking's help func always provide the clue that whelther it is ok to go next
public boolean dfs(StringBuilder sb, int n, int k, Set<String> visited) {
    if(visited.size() == total) return true;
    String prev = sb.toString().substring(sb.length()-n+1);
    
    for(int i = 0; i < k; i++) {
        String newCrack = prev+""+i;
        if(!visited.contains(newCrack)){
            visited.add(newCrack);
            sb.append(i);
            if(dfs(sb, n, k, visited)) return true;
            sb.delete(sb.length()-1, sb.length());
            visited.remove(newCrack);
        }
    }
    return false;
}