127. Word Ladder

image.png

image.png

转换成BFS做

image.png

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict;
        for(int i = 0; i < wordList.size(); i++){
            dict.insert(wordList[i]);
        }
        if(!dict.count(endWord)) return 0;
        dict.insert(endWord);
        queue<pair<string, int>> q;
        q.push(make_pair(beginWord,1));
        while(!q.empty()){
            string cur = q.front().first;
            // cout<<cur<<endl;
            int len = q.front().second;
            q.pop();
            vector<string> nb = findNeighbor(cur, dict);
            for(int i = 0; i < nb.size(); i++){
                if(nb[i] == endWord) return len+1;
                q.push(make_pair(nb[i], len+1));
            }
        }
        return 0;
    }
private:
    vector<string> findNeighbor(string x, unordered_set<string>& dict){
        vector<string> ret;
        for(int i = 0; i < x.length(); i++){
            char ch = x[i];
            for(int j = 0; j < 26; j++){
                x[i] = 'a' + j;
                if(dict.count(x)){
                    ret.push_back(x);
                    dict.erase(x);
                }
            }
            x[i] = ch;
        }
        return ret;
    }
};