C++, greedy loop from backward with explaination

  • 2

    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;
            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);
                        ans += to_string(j);
            return ans;

Log in to reply

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