Leetcode_127_Word Ladder

[lihe]

Word Ladder

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

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

Note:

• Return 0 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: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

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

Output: 0

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

算法思路：

1. 单词和单词之间的转换可以理解为一张图，图的定点为单词，若两个单词之间可以相互转换，则这两个单词代表的定点之间有一条边，题目求的是从beginword到endword的最短路径；
2. 使用map构造邻接表所表示的图，map定义为以string为key，vector<string>为value，将beginwordpush进wordlist，遍历wordlist，对任意两个单词，若它们只差一个字母，则将其相连；

bool connect(const std::string &word1, const std::string &word2){
    int cnt = 0;
    for(int i = 0; i < word1.size(); 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){
    wordList.push_back(beginWord);
    for(int i = 0; i < wordList.size(); i++){
        graph[wordList] = 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]);
            }
        }
    }
}

3. 设置搜索队列Q，队列节点为pair<定点，步数>；设置集合visit，记录搜索过的节点；将<beginWord, 1> 添加至队列；
4. 只要队列不空；取出队头元素：
   • 若取出的队头元素是endword，返回到达当前节点的步数；
   • 否则拓展该节点，将与该节点相连且未添加到visit中的节点与步数同时添加的到队列Q，并将拓展节点加入viist；
5. 若最终都无法到达endword则返回0；

int BFS_graph(std::string &beginWord, std::string &endWord,
              std::map<std::string, std::vector<std::string>> &graph){
    std::queue<std::pair<std::string, int>> Q;
    std::set<std::string> visit;
    Q.push(std::make_pair(beginWord, 1));
    visit.insert(beginWord);
    while(!Q.empty()){
        std::string node = Q.front().first;
        int step = Q.front().second;
        Q.pop();
        if(node == endWord){
            return step;
        }
        const std::vector<std::string> &neighbors = graph[node];
        for(int i = 0; i < neighbors.size(); i++){
            if(visit.find(neighbors[i]) == visit.end()){
                Q.push(std::make_pair(neighbors[i], step + 1));
                visit.insert(neighbors[i]);
            }
        }
    }
    return 0;
}

class Solution{
public:
    int ladderLength(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);
        return BFS_graph(beginWord, endWord, graph);
    }
};