753. Cracking the Safe

📋 Đề Bài

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 4^th digit.
- "01" is typed in starting from the 1^st digit.
- "10" is typed in starting from the 3^rd digit.
- "11" is typed in starting from the 2^nd digit.
Thus "01100" will unlock the safe. "10011", and "11001" would also unlock the safe.

Constraints:

1 <= n <= 4
1 <= k <= 10
1 <= kⁿ <= 4096

🧠 Thuật Toán & Kỹ Thuật

DFS (Tìm kiếm theo chiều sâu)Hash Table (Bảng băm)String (Chuỗi)

⏱️ Thời gian O(V+E)

💾 Không gian O(V)

💻 Lời Giải

C++ 0753-cracking-the-safe.cpp

class Solution {
private:
    string ans;
    int n, k;
    unordered_set<string> visited;
    vector<string> s;
    int m;
    
public:
    bool dfs(string last) {
        if (visited.size() == m) {
            return true;
        }
        for (char c = 0; c < k; ++c) {
            string tmp = last + char(c + '0');
            if (!visited.count(tmp)) {
                visited.insert(tmp);
                ans.push_back(c + '0');
                if (dfs(tmp.substr(1))) {
                    return true;
                }
                ans.pop_back();
                visited.erase(tmp);
            }
        }
        return false;
    }
    
    string crackSafe(int n, int k) {
        this->n = n;
        this->k = k;
        this->m = pow(k, n);
        string start = "";
        for (int i = 0; i < n - 1; ++i) {
            start.push_back('0');
        }
        ans = start;
        dfs(start);
        return ans;
    }
};