Recursive C++ solution with lots of comments - unlike others here, I won't write that it's easy.


  • 0
    G
    class Solution {
    public:
    
        //generate all combinations of words of size n with k letters
        vector<string> generateCombs(int n, int k){
    
            vector<string> result;
            
            if(n == 1){
                for(char i = '0'; i < '0' + k; ++i){
                    string tmp(1,i);
                    result.push_back(tmp);
                }
            }
            else{
                auto temp = generateCombs(n - 1,k);
                for(auto p : temp){
                    for(char i = '0'; i < '0'+ k; ++i){
                        string pt = p + string(1,i);
                        result.push_back(pt);
                    }
                }
            }
            
            return result;
        }
        
        //type declarations
        using sbpair = pair<string,bool>;
        using vsbpair = vector<sbpair>;
        
        //a hash map that will be used during the visit
        unordered_map<string,vsbpair> prefs;
        
        //
        //visit is a recursive function that attempts to find a Hamiltonian path 
        // betweem nodes where each node corresponds to a single n-sized word. 
        // An edge connects two nodes if and only if the first node's n-1th suffix corresponds
        // to the second node's n - 1th prefix.
        //
        bool visit(sbpair &p, string &res, size_t size){
            
            if(size == 1){
                res += p.first;
                return true;
            }
            
            p.second = true;
            string prevRes = res;
            res += p.first.substr(0,1);
            string ss = p.first.substr(1);
            
            for(auto &pr : prefs[ss]){
                if(!pr.second){
                    if(visit(pr,res,size - 1)){
                        return true;
                    }
                }
            }
            
            p.second = false;
            res = prevRes;
            return false;
        }
        
        string crackSafe(int n, int k) {
            
            //get all combinations of size n with k letters
            auto combs = generateCombs(n,k);    
            
            // The case of n = 1 is a special case as there are no overlapping 
            // prefixes and suffixes. In this case we just return a single string
            // which corresponds to all the 1 letter words found.
            if(n == 1){
                string res= 
                accumulate(combs.begin(),combs.end(),string(),[](string curr,const string &s){
                    curr += s; 
                    return curr;
                });
                
                return res;
            }
            
            //go through the combinations and add them to the prefs (prefixes) hashtable
            for(auto &c : combs){
                prefs[c.substr(0,n - 1)].push_back({c,false});
            }
    
            //pick the first word and find a hamiltonian path starting with it
            auto &vpair = *(prefs.begin()->second.begin());
            string result;
            visit(vpair,result,combs.size());
            return result;
        }
    };
    

Log in to reply
 

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