5.23  如何查找到达目标词的最短链长度

5.23 如何查找到达目标词的最短链长度

【出自JD面试题】

难度系数：★★★☆☆ 被考察系数：★★★☆☆

题目描述：

给定一个字典和两个长度相同的“开始”和“目标”的单词。找到从“开始”到“目标”最小链的长度。如果它存在，那么这条链中的相邻单词只有一个字符不同，而链中的每个单词都是有效的单词，即它存在于字典中。可以假设词典中存在“目标”字，所有词典词的长度相同。

例如：

给定一个单词字典为{pooN，pbcc，zamc，poIc，pbca，pbIc，poIN}

start=TooN

target=pbca

输出结果为7

因为TooN（start）-pooN-poIN-poIc-pbIc-pbcc-pbca（target）。

分析与解答：

本题主要的解决方法是：使用BFS的方式从给定的字符串开始遍历所有相邻（两个单词只有一个不同的字符）的单词，直到遍历找到目标单词或者遍历完所有的单词为止。实现代

码如下：

程序的运行结果为

最短的链条的长度为7

算法性能分析：

这种方法的时间复杂度为为O（n²m），其中，n为单词的个数，m为字符串的长度。