Leetcode_126_Word Ladder II

[lihe]

Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

struct Qitem{
    std::string node;
    int parent_pos;
    int step;
    Qitem(std::string _node, int _parent_pos, int _step): node(_node), parent_pos(_parent_pos), step(_step){}
};

class Solution{
public:
    std::vector<std::vector<std::string>> findLadders(std::string beginWord,
                                                      std::string endWord, std::vector<std::string> &wordList){
        std::map<std::string, std::vector<std::string>> graph;
        construct_graph(beginWord, wordList, graph);
        std::vector<Qitem> Q;
        std::vector<int> end_word_pos;
        BFS_graph(beginWord, endWord, graph, Q, end_word_pos);
        std::vector<std::vector<std::string>> result;
        for(int i = 0; i < end_word_pos.size(); i++){
            int pos = end_word_pos[i];
            std::vector<std::string> path;
            while(pos != -1){
                path.push_back(Q[pos].node);
                pos = Q[pos].parent_pos;
            }
            result.push_back(std::vector<std::string>());
            for(int j = path.size() - 1; j >= 0; j--){
                result[i].push_back(path[j]);
            }
        }
        return result;
    }
private:
    void BFS_graph(std::string &beginWord, std::string &endWord,
                   std::map<std::string, std::vector<std::string>> &graph,
                   std::vector<Qitem> &Q, std::vector<int> &end_word_pos){
        std::map<std::string, int> visit;
        int min_step = 0;
        Q.push_back(Qitem(beginWord, -1, 1));
        visit[beginWord] = 1;
        int front = 0;
        while(front != Q.size()){
            const std::string &node = Q[front].node;
            int step = Q[front].step;
            if(min_step != 0 && step > min_step){
                break;
            }
            if(node == endWord){
                min_step = step;
                end_word_pos.push_back(front);
            }
            const std::vector<std::string> &neighbors = graph[node];
            for(int i = 0; i < neighbors.size(); i++){
                if(visit.find(neighbors[i]) == visit.end() || visit[neighbors[i]] == step + 1){
                    Q.push_back(Qitem(neighbors[i], front, step + 1));
                    visit[neighbors[i]] = step + 1;
                }
            }
            front++;
        }
    }
    bool connect(const std::string &word1, const std::string &word2){  // 判断 word1 word2 是否可以转化
        int cnt = 0;
        for(int i = 0; i < word1.length(); i++){
            if(word1[i] != word2[i]){
                cnt++;
            }
        }
        return cnt == 1;
    }

    void construct_graph(std::string &beginWord, std::vector<std::string> &wordList,
                         std::map<std::string, std::vector<std::string>> &graph){
        int has_begin_word = 0;
        for(int i = 0; i < wordList.size(); i++){
            if(wordList[i] == beginWord){
                has_begin_word = 1;
            }
            graph[wordList[i]] = std::vector<std::string>();
        }
        for(int i = 0; i < wordList.size(); i++){
            for(int j = i + 1; j < wordList.size(); j++){
                if(connect(wordList[i], wordList[j])){
                    graph[wordList[i]].push_back(wordList[j]);
                    graph[wordList[j]].push_back(wordList[i]);
                }
            }
            if(has_begin_word == 0 && connect(beginWord, wordList[i])){
                graph[beginWord].push_back(wordList[i]);
            }
        }
    }
};