version of UPDATE (2017/1/20), C++,BFS


  • 0
    K

    This solution is accepted but tow slow. Can anyone help me make it faster?

    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
          
            unordered_map<string, int>wordMap;
            for(int i = 0; i < wordList.size(); i++) wordMap.insert(make_pair(wordList[i], 0));
            
            if(wordMap.find(endWord) == wordMap.end()) return 0;
            
            queue<pair<string, int>> q;
            q.push(make_pair(beginWord, 1));
            while(!q.empty()) {
                string temp = q.front().first;
                int dist = q.front().second;
                q.pop();
                wordMap.erase(temp);
                for(int i = 0; i < temp.size(); i++) {
                    char letter = temp[i];
                    for(int j = 0; j < 26; j++) {
                        temp[i]= 'a' + j;
                        if(temp == endWord) return dist + 1;
                        if(wordMap.find(temp) != wordMap.end()) {
                            if(!wordMap[temp]) q.push(make_pair(temp, dist + 1));
                        }
                    }
                    temp[i] = letter;
                }
                
            }
            return 0;
        } 
    };
    

  • 0
    Z

    you can use unordered_set<string> instead of unordered_map<string>


Log in to reply
 

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