Using BFS to solve a hard problem

126. Word Ladder II

Explanation

This is a hard problem in leetcode which can be solved by the BFS. Usually the BFS can be used to find the shortest path problem and most case only the cost of the path should be returned. For this problem, all shortest path should be found. Based on this, we need extra trick on maintaining the seen set. The basic idea is:

• Keep a seen for all previous levels.
• For the current level, maintain a temp seen and this temp seen will not influence the exploration of current level (one node may be visited multiple times from different paths where they have the same depth, for example: ABE; CDE)
• After traversing the current level, add the temp seen to the seen.

Based on this, key steps will be

• Build the graph
• BFS with specially designed seen.

Reference Code

class Solution {
    public:
    vector<string> words;
    int dis(int i, int j){
        int ret = 0;
        for (int k = 0; k < words[i].size(); ++k){
            ret += words[i][k] != words[j][k];
        }
        return ret;
    }
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        wordList.push_back(beginWord);
        unordered_set<string> s(wordList.begin(), wordList.end());
        if (s.find(endWord) == s.end()) return {};
        vector<string> words(s.begin(), s.end());
        unordered_map<string, vector<string>> graph;
        const int n = words.size();
        this -> words = words;
        // Build graph
        for (int i = 0; i < n - 1; ++i){
            for (int j = i + 1; j < n; ++j){
                if (dis(i, j) == 1){
                    graph[words[i]].push_back(words[j]);
                    graph[words[j]].push_back(words[i]);
                }
            }
        }
        vector<vector<string>> ret;
        // BFS
        int shortestLevel = INT_MAX;
        vector<vector<string>> currentLevel;
        currentLevel.push_back({beginWord});
        int level = 1;
        unordered_set<string> seen;
        seen.insert(beginWord);
        while (!currentLevel.empty()){
            vector<vector<string>> newLevel;
            // keep a this seen for this level and add those seen members after the traverse of this level as we may visit the same element multiple times only if they are on the same level.
            unordered_set<string> thisseen;
            for (auto words: currentLevel){
                for (auto nei: graph[words.back()]){
                    vector<string> newWords = words;
                    if (seen.find(nei) != seen.end()) {
                        continue;
                    }
                    if (nei == endWord && level + 1 <= shortestLevel){
newWords.push_back(nei);
                        ret.push_back(newWords);
                        shortestLevel = level + 1; 
                    } else if (nei != endWord && level + 1 < shortestLevel){
                        newWords.push_back(nei);
                        newLevel.push_back(newWords);
                        thisseen.insert(nei);
                    }
                }
}
            for (auto word: thisseen) seen.insert(word);
            level++;
            currentLevel = newLevel;
        }
        return ret;   
    }
};

Run time

Runtime: 84 ms, faster than 13.20% of C++ online submissions for Word Ladder II.
Memory Usage: 20.9 MB, less than 14.77% of C++ online submissions for Word Ladder II.

Reference

[1]https://jimmy-shen.medium.com/word-ladder-ii-bfs-7ec9f2b0a29b