LeetCode 127. Word Ladder 宽度优先搜索+二分

class Node{
public:
    string word;
    int len;
    
    Node(string w, int l){
        word = w, len = l;
    }
};
//unordered_map 可以当做标记数组使用
//c++ stl binary__search, 判断元素是否存在,注意不会返回下标,返回下标的是lower_bound和upper_bound
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, bool> m;
        queue<Node> que;
        
        Node startNode(beginWord, 1);
        m[beginWord] = true;
        que.push(startNode);
        sort(wordList.begin(), wordList.end());
        
        while (!que.empty()){
            Node curNode = que.front();
            que.pop();
            string curWord = curNode.word;
            
            for (int i = 0; i < curWord.size(); ++i){
                for (char j = 'a'; j <= 'z'; ++j){
                    if (j == curWord[i]){
                        continue;
                    }
                    
                    string nextWord = curWord;
                    nextWord[i] = j;
                    
                    if (binary_search(wordList.begin(), wordList.end(), nextWord) == false){
                        continue;
                    }
                    
                    if (nextWord == endWord){
                        return curNode.len + 1;
                    }
                    
                    if (binary_search(wordList.begin(), wordList.end(), nextWord) == true && m[nextWord] == false){
                        m[nextWord] = true;
                        Node nextNode(nextWord, curNode.len + 1);
                        que.push(nextNode);
                    }
                }
            }
        }
        
        return 0;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部