[word ladder II] why my code got memory limit exceeded? (using BFS+hashtable)


  • 0
    S

    Hi,
    I am now trying to use BFS + hashtable to solve this problem.
    Can anyone help me to take a look at my code? where can I optimize to reduce memory usage?
    Basically I am using these data structures:

        vector<string> wordList;  // keep all the words in a list
        unordered_map<string, int> wordIndexMap;  store the index of a word in wordlist
        unordered_map<string, vector<int>> wordParrentMap;     
            // use this to keep track of the word's parrent during BFS search
    

    also, this data structure is stored in the queue to keep the level of the BFS search

    typedef struct _tagWordLvlPair{
        string word;
        int lvl;
    }WordLvlPair;
    

    Here is my detailed code..
    Thanks

    class Solution {
    private:
            vector<string> wordList;
            unordered_map<string, int> wordIndexMap;
            unordered_map<string, vector<int>> wordParrentMap;     // use this to keep track of the word's parrent during BFS search
            int found;
        typedef struct _tagWordLvlPair{
            string word;
            int lvl;
        }WordLvlPair;
        
        void updateQue(WordLvlPair wlpair, unordered_set<string> &unusedWord, 
                       queue<WordLvlPair> &que, vector<int> &curLvlWordIndex, string &end, unordered_set<string> &hit){
            
            string curStr=wlpair.word;
            WordLvlPair newPair;
            newPair.lvl=wlpair.lvl+1;
            int parrentIndex=wordIndexMap[curStr];
            
            for(int i=0; i<curStr.size(); ++i){
                int tmp=curStr[i]-'a';
                for(int j=0; j<26; ++j){
                    //update the word's parrents & update queue
                    if(j==tmp) continue;
                    curStr[i]=('a'+j);
                    if(unusedWord.count(curStr)){
                        if(hit.count(curStr)==0){
                            que.push(newPair); //curStr 已经被访问过了
                            hit.insert(curStr);
                        }   
                        newPair.word=curStr;
                        (wordParrentMap[curStr]).push_back(parrentIndex);
                        curLvlWordIndex.push_back(wordIndexMap[curStr]);
                        
                        if(curStr==end) found=1;
                    }
                }
                curStr[i]='a'+tmp;
            }
            
            return;
        }
        
        void updatePath(string &start, string &end, vector<string> &curRes, vector<vector<string>> &finalRes){
            if(start==end){
                finalRes.push_back(curRes);
                return;
            }
            vector<int> parrentIndex = wordParrentMap[end];
            for(int i=0; i<parrentIndex.size(); ++i){
                curRes.insert(curRes.begin(), wordList[parrentIndex[i]]);
                updatePath(start, wordList[parrentIndex[i]], curRes, finalRes);
                curRes.erase(curRes.begin());
            }
            
            return;
        }
    
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            vector<vector<string>> res;
            vector<string> curres;
            dict.insert(start);  // tricky
            dict.insert(end);    // tricky..
            unordered_set<string> unusedWord=dict;              // keep unused words
            unordered_set<string> hit;
    
            wordList.clear();
            wordIndexMap.clear();
            wordParrentMap.clear();                             // use this to keep track of the word's parrent during BFS search
            vector<int> emptyArray;
            
            for(const auto& elem: dict)     // put all words in a list.
                wordList.push_back(elem);
            for(int i=0; i<wordList.size(); ++i)                // make a map from string->index in list
                wordIndexMap[wordList[i]]=i;
            for(int i=0; i<wordList.size(); ++i)
                wordParrentMap[wordList[i]]=emptyArray;         // hard copy.
                
            queue<WordLvlPair> que;
            
            if(dict.size()>100) return res;  // protection.
            
            //if(LadderLen(start, end, dict)==-1) return res;     // no ladder..
            
            WordLvlPair wlpair;
            wlpair.word=start;
            wlpair.lvl=0;
            que.push(wlpair); // add first in queue
            unusedWord.erase(start);    //tricky
            
            vector<int> curLvlWordIndex;
            int curLvl=1;   // 正在遍历的层数, 因为第0层是start 所以开始对队列操作时,其实是遍历的第一层
            found=0;
            while(!que.empty()){  // do BFS
                //find all the words that has distance of 1 with the head
                wlpair=que.front();
                que.pop();
                
                if(!curLvlWordIndex.empty()&&(wlpair.lvl!=curLvl)){
                    //remove all current level
                    //updated unusedWord
                    for(int i=0; i<curLvlWordIndex.size(); ++i){
                        unusedWord.erase(wordList[curLvlWordIndex[i]]);
                    }
                    curLvlWordIndex.clear();
                    curLvl++;
                    if(found) break;
                }
                //find all the words that has distance of 1 with the head in the unsuedword
                updateQue(wlpair, unusedWord, que, curLvlWordIndex, end, hit);
                //update the word's parrents
            }
            
            if (found){
                curres.insert(curres.begin(), end);
                updatePath(start, end, curres, res);
            }
            return res;
        }
    };

Log in to reply
 

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