C++, greedy loop from backward with explaination


  • 2
    W

    Taking n = 2,k= 2 as example, we start with "00", let string prev = last n-1 digits (prev = '0'), and create an new string by appending a new digit from k-1 to 0 respectively. in this case we first check string '01'.
    for each string, we use an unordered_set to check if visited. if valid then we append another digit until the end.

    string crackSafe(int n, int k) {
            string ans = string(n, '0');
            unordered_set<string> visited;
            visited.insert(ans);
            
            for(int i = 0;i<pow(k,n);i++){
                string prev = ans.substr(ans.size()-n+1,n-1);
                for(int j = k-1;j>=0;j--){
                    string now = prev + to_string(j);
                    if(!visited.count(now)){
                        visited.insert(now);
                        ans += to_string(j);
                        break;
                    }
                }
            }
            return ans;
        }
    

Log in to reply
 

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