127. 单词接龙

127. 单词接龙

bfs+优化建图

class Solution {
public:
    set<string>wl;
    unordered_map<string, int>w2i;
    vector<vector<int>>g;
    int idx;
    void add_word(string s,string t){
        if(!w2i.count(s)){
            w2i[s]=idx++;
            g.push_back(vector<int>());
        }
        if(!w2i.count(t)){
            w2i[t]=idx++;
            g.push_back(vector<int>());
        }
        int sid=w2i[s], tid=w2i[t];
        g[sid].push_back(tid);
        g[tid].push_back(sid);
    }
    void add_edge(string word){
        for(int i=0;i<word.size();i++){
            string tmp=word;
            tmp[i]='*';
            add_word(word,tmp);
        }
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for(auto w:wordList)wl.insert(w);
        idx=0;
        add_edge(beginWord);
        if(!wl.count(endWord))return 0;
        for(auto w:wl)add_edge(w);

        queue<int>Q;
        Q.push(w2i[beginWord]);
        int dist[w2i.size()+10];
        memset(dist,0x3f,sizeof dist);
        dist[0]=0;

        while(Q.size()){
            int u=Q.front();
            Q.pop();
            for(int nxt:g[u]){
                if(dist[nxt] > dist[u]+1){
                    dist[nxt] = dist[u]+1;
                    Q.push(nxt);
                }
            }
        }
        if(dist[w2i[endWord]]==0x3f3f3f3f)return 0;
        return dist[w2i[endWord]]/2+1;
    }
};