My 30 lines C++ only beats 96.86%!


  • 0
    K
    int ladderLength(string beginWord, string endWord, vector<string>& wordDict) {
            unordered_set<string> word_dict_;
            for (auto &word : wordDict) word_dict_.insert(word);
            if (word_dict_.find(endWord) == word_dict_.end()) return 0;
            else word_dict_.erase(endWord);
            unordered_set<string> q1, q2, temp;
            q1.insert(beginWord);
            q2.insert(endWord);
            int count = 0;
            while (!q1.empty() && !q2.empty()) {
                ++count;
                if (q1.size() > q2.size()) swap(q1, q2);
                temp.clear();
                for (auto word_ : q1) {
                    for (int j = 0; j < word_.size(); ++j) {
                        char hold = word_[j];
                        for (char i = 'a'; i <= 'z'; ++i) {
                            word_[j] = i;
                            if (q2.find(word_) != q2.end())  return count + 1;
                            if (word_dict_.find(word_) != word_dict_.end()) {
                                word_dict_.erase(word_);
                                temp.insert(word_);
                            }
                        }
                        word_[j] = hold;
                    }
                }
                swap(q1, temp);
            }
            return 0;
        }
    

Log in to reply
 

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