LeetCode每日一题：单词接龙
传送门 题目描述 给定一个起始单词，一个目标单词与一个备选字典，通过以下规则将起始单词变到目标单词去： 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 求最短变化步数。 思路 看到最短步数，首先想到BFS。但使用BFS的前提是有一个可以用来搜索的图或者树，于是思维转向如何建立图/树。 思路还是很清晰的：任何两个只差一个字母的单词之间可以连成一条无向边，所有的边共同构成整张单词图。建成图后再判断endWord是否在图中就行了。真正复杂的地方在实现。 单个的字符串并不好节点化，我们可以把每个单词映射为一个id值，然后用一个int的邻接矩阵来存储整个词图。 对于添加边的操作，朴素思路枚举每一对单词，判断它们之间是否可以存在一条边，如果是，则将其加入词图，但这样显然太慢了。 可以考虑构造间接节点。假设当前单词为hit，那么显然地，_it、h_t、hi_三个长相的单词都可以与hit连成一条边。那么我们只需要构造出这三个间接节点，然后将当前单词连在间接节点上就行了。不难得知，每一个可以与hit连边的单词都一定会连向这三个间接节点。 值得注意的是，这样的操作虽然节省了时间，但人为的增加了一些“不需要的边”。假设有两个相邻单词，他们原来可以直达彼此，现在需要通过间接节点来访问，所以说真实的步数应该等于当前步数/2。又因为初始化时会将beginWord也加入词图，所以最后的总步数还得额外的+1。 代码 ```cpp class Solution { public: unordered_map wordId; vector> mp; int idNum = 0; void addWord(string& str) { if(!wordId.count(str)) { wordId[str] = idNum++; mp.emplace_back(); } } void addEdge(string& …