C++, DFS, 3 ms


  • 2
    Z
    class Solution {
    public:
        string crackSafe(int n, int k) {
            string ans(n, '0');
            if (k == 1) return ans;
            int N = 10000;
            vector<int> visited(N, 0);
            ans += '1'; // starting with "0..01" due to symmetry
            visited[0] = 1;
            visited[1] = 1;
            int len = pow(k, n)+(n-1); //length of answer
            helper(visited, ans, n, k, len);
            return ans;
        }
    private:
        bool helper(vector<int>& visited, string& ans, int n, int k, int len) {
            if (ans.size() == len) return true;
            ans += '0';
            for (int i = 0; i < k; i++) {
                ans.back() = i + '0';
                int t = stoi(ans.substr(ans.size()-n, n));
                if (visited[t] == 0) {
                    visited[t] = 1;
                    if (helper(visited, ans, n, k, len)) return true;
                    visited[t] = 0;
                }
            }
            ans.pop_back();
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.