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.

class Solution {
    unordered_set<int> visited;
    int makeKey(string& str, int n) {
        int res = 0;
        for(int i = str.length() - n + 1; i < str.length(); i++) {
            res = res * 10 + (str[i] & 0b1111);
        }
        return res;
    }
    bool backTracking(string& res, int& ma, int n, int k) {
        if(visited.size() == ma) return true;
        int key = makeKey(res, n);
        for(int i = 0; i < k; i++) {
            if(visited.count(key * 10 + i)) continue;
            res += (i | 0b110000);
            visited.insert(key * 10 + i);
            if(backTracking(res, ma, n, k)) return true;
            res.pop_back();
            visited.erase(key * 10 + i);
        }
        return false;
    }
public:
    string crackSafe(int n, int k) {
        string res = string(n,'0');
        visited.insert(0);
        int ma = pow(k,n);
        backTracking(res,ma,n,k);
        return res;
    }
};