传送门

题目描述

给定一个起始单词，一个目标单词与一个备选字典，通过以下规则将起始单词变到目标单词去：

  1. 每次转换只能改变一个字母。
  2. 转换过程中的中间单词必须是字典中的单词。

求最短变化步数。

思路

看到最短步数，首先想到BFS。但使用BFS的前提是有一个可以用来搜索的图或者树，于是思维转向如何建立图/树。

思路还是很清晰的：任何两个只差一个字母的单词之间可以连成一条无向边，所有的边共同构成整张单词图。建成图后再判断endWord是否在图中就行了。真正复杂的地方在实现。

单个的字符串并不好节点化，我们可以把每个单词映射为一个id值，然后用一个int的邻接矩阵来存储整个词图。

对于添加边的操作，朴素思路枚举每一对单词，判断它们之间是否可以存在一条边，如果是，则将其加入词图，但这样显然太慢了。

可以考虑构造间接节点。假设当前单词为hit，那么显然地，_it、h_t、hi_三个长相的单词都可以与hit连成一条边。那么我们只需要构造出这三个间接节点，然后将当前单词连在间接节点上就行了。不难得知，每一个可以与hit连边的单词都一定会连向这三个间接节点。

值得注意的是，这样的操作虽然节省了时间，但人为的增加了一些“不需要的边”。假设有两个相邻单词，他们原来可以直达彼此，现在需要通过间接节点来访问，所以说真实的步数应该等于当前步数/2。又因为初始化时会将beginWord也加入词图，所以最后的总步数还得额外的+1。

代码

class Solution {
public:
    unordered_map<string, int> wordId;
    vector<vector<int>>  mp;
    int idNum = 0;

    void addWord(string& str) {
        if(!wordId.count(str)) {
            wordId[str] = idNum++;
            mp.emplace_back();
        }
    }

    void addEdge(string& str) {
        addWord(str);
        int idu = wordId[str];
        for(char& ch : str) {
            char tmp = ch;
            ch = '*';
            addWord(str);
            int idv = wordId[str];
            mp[idu].push_back(idv);
            mp[idv].push_back(idu);
            ch = tmp;
        }
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for(string& str : wordList) {
            addEdge(str);
        }addEdge(beginWord);   

        if(!wordId.count(endWord)) return 0;

        vector<int> dis(idNum, INT_MAX);
        int beginId = wordId[beginWord], endId = wordId[endWord];
        dis[beginId] = 0;

        queue<int> que;
        que.push(beginId);
        while(!que.empty()) {
            int now = que.front();que.pop();
            
            if(now == endId) {
                return dis[endId] / 2 + 1;
            }

            for(int& it : mp[now]) {
                if(dis[it] == INT_MAX) {
                    dis[it] = dis[now] + 1;
                    que.push(it);
                } 
            }
        }

        return 0;
    }
};