LC127. Word Ladder

This is quite a hard one to me. Very good one as well.

Java:

public int ladderLength(String b, String e, List<String> dict) {
    Queue<String> q = new LinkedList<>();
    q.add(b);
    q.add(null);
    
    // Mark visited word
    Set<String> visited = new HashSet<>();
    visited.add(b);
    
    int level = 1;
    
    while (!q.isEmpty()) {
        String str = q.poll();
        
        if (str != null) {
            for (int i = 0; i < str.length(); ++i) {
                char[] chars = str.toCharArray();
                
                for (char c='a'; c<='z'; ++c) {
                    chars[i] = c;
                    
                    String word = new String(chars);
                    // dict.contains(word) : last word
                    if (word.equals(e) && dict.contains(word)) return level + 1;
                    
                    // Put into queue
                    if (dict.contains(word) && !visited.contains(word)) {
                        q.add(word);
                        visited.add(word);
                    }
                }
            }
        } else {
            level++;
            // new level finished adding elements
            if (!q.isEmpty()) q.add(null);
        }
    }
    
    return 0;
}

But, it gets a TLE in 2020. OJ only passes bi-directional BFS now:

C++:

unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;
    
    unordered_set<string> q1{beginWord};
    unordered_set<string> q2{endWord};
    
    int len = beginWord.length();
    int step = 0;
    
    while (!q1.empty() && !q2.empty()) {
        ++step;
        
        // always expand the smaller queue first : q1
        if (q1.size() > q2.size()) 
            std::swap(q1, q2);
        
        unordered_set<string> q;
        
        for (string w : q1) {
            for (int i=0; i<len; ++i) {
                char ch = w[i];
                for (int j='a'; j<='z'; ++j) {
                    w[i] = j;
                    // q2存在这个w,说明两个bfs的graph汇合了
                    if (q2.count(w)) return step + 1;
                    if (!dict.count(w)) continue;
                    dict.erase(w);
                    q.insert(w);
                }
                w[i] = ch;
            }
        }
        
        std::swap(q, q1);
    }
    
    return 0;
}