Cracking the Safe - LeetCode solutions

Problem

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 (Java)

class Solution {
    private String foundStr;

    public String crackSafe(int n, int k) {
        int targetCnt = (int) Math.pow(k, n);
        boolean[] visited = new boolean[(int) Math.pow(10, n)];
        visited[0] = true;
        int visitedCnt = 1;
        StringBuilder crackStr = new StringBuilder();
        for (int i = 0; i < n; i++) {
            crackStr.append('0');
        }
        dfsAddPwd(n, k, crackStr, 0, visited, visitedCnt, targetCnt);
        return foundStr;
    }

    private void dfsAddPwd(
            int n,
            int k,
            StringBuilder crackStr,
            int prev,
            boolean[] visited,
            int visitedCnt,
            int targetCnt) {
        if (foundStr != null) {
            return;
        }
        if (visitedCnt == targetCnt) {
            foundStr = crackStr.toString();
            return;
        }
        int root = 10 * prev % ((int) Math.pow(10, n));
        for (int i = 0; i < k; i++) {
            int current = root + i;
            if (!visited[current]) {
                crackStr.append(i);
                visited[current] = true;
                dfsAddPwd(n, k, crackStr, current, visited, visitedCnt + 1, targetCnt);
                crackStr.setLength(crackStr.length() - 1);
                visited[current] = false;
            }
        }
    }
}

Solution (C++)

class Solution {
public:
    string crackSafe(int n, int k) {
        const int total_len = pow(k, n) + n - 1;
        string ans(n, '0');
        unordered_set<string> visited{ans};
        if (dfs(ans, total_len, n, k, visited))
            return ans;
        return "";
    }
private:
    bool dfs(string& ans, const int total_len, const int n, const int k, unordered_set<string>& visited) {
        if (ans.length() == total_len)
            return true;

        string node = ans.substr(ans.length() - n + 1, n - 1);
        for (char c = '0'; c < '0' + k; ++c) {
            node.push_back(c);
            if (!visited.count(node)) {
                ans.push_back(c);
                visited.insert(node);
                if (dfs(ans, total_len, n, k, visited)) return true;
                visited.erase(node);
                ans.pop_back();
            }
            node.pop_back();
        }

        return false;
    }
};

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).