Word Ladder I & II (Leetcode 127

Word Ladder I:
https://leetcode.com/problems/word-ladder/

对于I，BFS层序遍历就行。为避免重复遍历，wordDict将找到的neighbor单词删掉。同时，找到下一个合适的单词(one character away) 的办法，是遍历该单词所有字符，将其替换成另外25个，然后查找WordDict，看新单词是否存在。

int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        wordList.insert(endWord);
        queue<pair<string, int>> q;
        q.push({beginWord, 1});
        while(!q.empty()){
            string cur = q.front().first; 
            int lvl = q.front().second; q.pop();
            if(cur == endWord) return lvl;
            vector<string> neighbors = findNeighbors(cur, wordList);
            for(string it : neighbors){
                q.push({it, lvl+1});
            }
        }
        return 0;
    }
    
    vector<string> findNeighbors(string cur, unordered_set<string>& wordList){
        vector<string> ret;
        for(int i=0; i<cur.length(); i++){
            char c = cur[i];
            for(int j=0; j<26; j++){
                if('a'+j == c) continue;
                cur[i] = 'a'+j;
                if(wordList.count(cur)){
                    ret.push_back(cur);
                    wordList.erase(cur);
                }
            }
            cur[i] = c;
        }
        return ret;
    }

Word Ladder II:
https://leetcode.com/problems/word-ladder-ii/

II 则非常复杂，是leetcode里面acceptance非常低的题目之一。难点在于要返回所有的最短路径。不仅DFS搜索，还要选择最短的。
九章的思路是建立在 I 的基础上，从endWord开始往回BFS (同 I 一样)。这样的目的是建立每个单词与endWord的最短距离。然后再从起点DFS，每次判断neighbor 单词的距离是否小1，只有小1，才加入result set继续往下搜索。

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        vector<vector<string>> allcomb;
        wordList.insert(beginWord);
        wordList.insert(endWord);
        unordered_map<string, int> mp;
        unordered_map<string, vector<string>> nexts;
        bfs(endWord, wordList, mp, nexts);
        /*for(auto it : mp){
            cout << it.first << " " << it.second << endl;
        }*/
        vector<string> comb;
        comb.push_back(beginWord);
        dfs(allcomb, comb, mp, nexts, beginWord, endWord);
        return allcomb;
    }
    
    void dfs(vector<vector<string>> &allcomb, vector<string> &comb, unordered_map<string, int> &mp, unordered_map<string, vector<string>> &nexts, string cur, string end){
        
        if(cur == end){
            allcomb.push_back(comb);
            return;
        }
        vector<string> neighbors = nexts[cur];
        for(int i=0; i<neighbors.size(); i++){
            if(mp[neighbors[i]] == mp[cur]-1){
                comb.push_back(neighbors[i]);
                dfs(allcomb, comb, mp, nexts, neighbors[i], end);
                comb.pop_back();
            }
        }
    }
    
    void bfs(string end, unordered_set<string> &dict, unordered_map<string, int> &mp, unordered_map<string, vector<string>> &nexts){
        queue<pair<string, int>> q;
        q.push({end, 0});
        mp[end] = 0;
        while(!q.empty()){
            string cur = q.front().first;
            int lvl = q.front().second; q.pop();
            vector<string> neighbors = findNeighbors(cur, dict);
            for(int i=0; i<neighbors.size(); i++){
                nexts[neighbors[i]].push_back(cur);
                if(!mp.count(neighbors[i])){
                    mp[neighbors[i]] = lvl+1;
                    q.push({neighbors[i], lvl+1});
                }
            }
        }
    }
    
    vector<string> findNeighbors(string cur, unordered_set<string> &dict){
        vector<string> ret;
        for(int i=0; i<cur.length(); i++){
            char c = cur[i];
            for(int j=0; j<26; j++){
                if('a' + j == c) continue;
                cur[i] = 'a' + j;
                if(dict.count(cur)){
                    ret.push_back(cur);
                }
            }
            cur[i] = c;
        }
        return ret;
    }
};

注意细节：要设 mp[end] = 0，并insert beginWord to set;