Word ladder

I: Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

II: Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

func ladderLength(beginWord string, endWord string, wordList []string) int {
    wordMap := getWordMap(wordList, beginWord)
    que := []string{beginWord}
    depth := 0
    for len(que) > 0 {
        depth++

        qlen := len(que)
        for i := 0; i < qlen; i++ {
            word := que[0]
            que = que[1:]

            candidates := getCandidates(word)
            for _, candidate := range candidates {
                if _, ok := wordMap[candidate]; ok {
                    if candidate == endWord {
                        return depth + 1
                    }

                    delete(wordMap, candidate)
                    que = append(que, candidate)
                }
            }
        }
    }
    return 0
}

func getWordMap(wordList []string, beginWord string) map[string]int {
    wordMap := make(map[string]int)
    for i, word := range wordList {
        if _, ok := wordMap[word]; !ok {
            if word != beginWord {
                wordMap[word] = i
            }
        }
    }
    return wordMap
}

func getCandidates(word string) []string {
    var res []string
    for i := 0; i < 26; i++ {
        for j := 0; j < len(word); j++ {
            if word[j] != byte(int('a')+i) {
                res = append(res, word[:j]+string(int('a')+i)+word[j+1:])
            }
        }
    }
    return res
}

C++ for II

    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        //very interesting problem
        //It can be solved with standard BFS. The tricky idea is doing BFS of paths instead of words!
        //Then the queue becomes a queue of paths.
        vector<vector<string>> ans;
        queue<vector<string>> paths;
        wordList.insert(endWord);
        paths.push({beginWord});
        int level = 1;
        int minLevel = INT_MAX;
        
        //"visited" records all the visited nodes on this level
        //these words will never be visited again after this level 
        //and should be removed from wordList. This is guaranteed
        // by the shortest path.
        unordered_set<string> visited; 
        
        while (!paths.empty()) {
            vector<string> path = paths.front();
            paths.pop();
            if (path.size() > level) {
                //reach a new level
                for (string w : visited) wordList.erase(w);
                visited.clear();
                if (path.size() > minLevel)
                    break;
                else
                    level = path.size();
            }
            string last = path.back();
            //find next words in wordList by changing
            //each element from 'a' to 'z'
            for (int i = 0; i < last.size(); ++i) {
                string news = last;
                for (char c = 'a'; c <= 'z'; ++c) {
                    news[i] = c;
                    if (wordList.find(news) != wordList.end()) {
                    //next word is in wordList
                    //append this word to path
                    //path will be reused in the loop
                    //so copy a new path
                        vector<string> newpath = path;
                        newpath.push_back(news);
                        visited.insert(news);
                        if (news == endWord) {
                            minLevel = level;
                            ans.push_back(newpath);
                        }
                        else
                            paths.push(newpath);
                    }
                }
            }
        }
        return ans;
    }