如何实现三位字符串最短转换序列查找算法？

你要实现的是固定三位长度字符串的最短转换序列，本质是无权无向图的最短路径搜索问题，每一个合法单词是图的节点，两个仅差1个字符的单词之间存在无向边，最短路径就是你要的结果，这类问题首选BFS（广度优先搜索）实现，因为BFS第一次遍历到终点时的路径天然就是最短的。

可以用TrieMap实现，但它是可选的优化方案，不是必须的：

• TrieMap的作用是优化「查找和当前单词仅差1个字符的所有合法单词」的步骤：由于单词固定为3位，当你要找和当前单词（比如ABC）差1位的单词时，可以分别匹配?BC/A?C/AB?三种模式，用提前构建好的单词前缀树可以快速捞出符合模式的所有合法单词，在words数组规模很大（比如十万级以上）的时候，效率远高于遍历整个数组计算汉明距离。
• 如果words规模很小（比如千级以内），直接遍历所有单词、计算和当前单词的不同字符数是否为1即可，代码实现更简单，没必要额外引入TrieMap。

你提到的逐一遍历words找差1字符单词的思路是可行的，结合BFS就可以实现，步骤如下：

• 边界处理：如果start和end相等，直接返回空列表；如果end不在words中，直接返回null
• 预处理：将words转为哈希集合，一方面可以O(1)判断单词是否合法，另一方面用来记录已访问的单词，避免重复走路径
• BFS初始化：队列存储的元素是「从start到当前节点的完整路径」，初始队列放入[start]，同时将start从访问集合中移除
• 逐层遍历队列：
  • 取出当前层的所有路径
  • 对每条路径的最后一个单词，生成所有仅差1个字符的三位字符串
  • 如果生成的字符串等于end，直接返回「当前路径+end」，就是最短转换序列
  • 如果生成的字符串在访问集合中，就将「当前路径+该字符串」加入下一层队列，同时将该字符串从访问集合移除（BFS第一次访问到该节点的路径就是最短的，后续无需再处理）
• 队列遍历完成仍未找到end，返回null

针对你给出的输入：start = "ABC"，end = "DEF"，words = ["ABC", "XZZ", "AEC", "DEF", "AEF"]，执行流程如下：

初始队列：[["ABC"]]，访问集合：{"XZZ", "AEC", "DEF", "AEF"}
第一层处理路径["ABC"]，匹配到差1位的合法单词AEC，生成新路径["ABC", "AEC"]加入队列，AEC从集合移除
第二层处理路径["ABC", "AEC"]，匹配到差1位的合法单词AEF，生成新路径["ABC", "AEC", "AEF"]加入队列，AEF从集合移除
第三层处理路径["ABC", "AEC", "AEF"]，匹配到差1位的合法单词DEF，刚好是终点，直接返回路径["ABC", "AEC", "AEF", "DEF"]，和预期结果一致

内容的提问来源于stack exchange，提问作者user17590816