Sharing my 272ms C++ solution


  • 1
    T
    class Solution {
    private:
        vector<vector<string>> result; // the result to be returned
        vector<string> path; // to store the temporary path (from the end to the start)
        unordered_map<string, vector<string>> myMap; // to store the reversed paths
        
        void getChildren(string s, unordered_set<string>& next, unordered_set<string>& wordList)
        {
            for(int i=0; i<s.length(); i++)
            {
                string temp = s;
                for(int j=0; j<26; j++)
                {
                    temp[i] = j+'a';
                    if(wordList.count(temp)>0)
                    {
                        next.insert(temp);
                        myMap[temp].push_back(s);
                    }
                }
            }
        }
        
        void printPath(string beginWord, string endWord)
        {
            path.push_back(endWord);
            
            if(endWord==beginWord)
            {
                reverse(path.begin(), path.end());
                result.push_back(path);
                reverse(path.begin(), path.end());
            }
            else if(myMap.count(endWord)>0)
            {
                vector<string> v = myMap[endWord];
                for(int i=0; i<v.size(); i++)
                    printPath(beginWord, v[i]);
            }
            
            path.pop_back();
        }
        
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
            wordList.insert(beginWord);
            wordList.insert(endWord);
            
            unordered_set<string> current;
            unordered_set<string> next;
            current.insert(beginWord);
            
            while(current.size()>0)
            {
                if(current.count(endWord)>0)
                {
                    printPath(beginWord, endWord);
                    return result;
                }
                    
                for(auto x=current.begin(); x!=current.end(); x++)
                    wordList.erase(*x);
                    
                for(auto y=current.begin(); y!=current.end(); y++)
                {
                    string s = *y;
                    getChildren(s, next, wordList);
                }
                current.clear();
                current = next;
                next.clear();
            }
            
            return result;
        }
    };

  • 0
    S

    Awesome job, I solved it but kept getting the time limit exceeded with words larger than 5 characters, and could not figure out why...I was actually comparing every word to every other word in the string instead of using character permutations and just checking if the word is in the set or no...Thanks for the answer!


  • 0
    Y

    one of dict.insert(endWord) should be dict.insert(beginWord);


  • 0
    T

    Thank you for pointing it out. I appreciate it and I've fixed it.


Log in to reply
 

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