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

  • 0
    class Solution {
        //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);
                auto temp = generateCombs(n - 1,k);
                for(auto p : temp){
                    for(char i = '0'; i < '0'+ k; ++i){
                        string pt = p + string(1,i);
            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(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;
            return result;

Log in to reply

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