题目描述
给定两个单词 (beginWord和endWord)以及一个单词列表，求从beginWord到endWord的转化序列的最短长度。
转化序列需要满足：
每次只能改变一个字母；
转化过程中的单词，必须出现在单词列表中（除了beginWord之外）；
注意：
如果不存在任何转化方案，请返回0；
数据中所有单词的长度均相等；
所有单词仅包含小写英文字母；
beginWord和endWord均非空，且不相等；
样例1
输入：
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出：
5
样例2
输入：
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出：
0
解释：由于cog不在单词列表中，所以不存在任何转化方案。
(最短路,BFS) O(n2L)O(n2L)
我们对问题进行抽象：
将单词看做点，如果两个单词可以相互转化，则在相应的点之间连一条无向边。那问题就变成了求从起点到终点的最短路。
由于边权都相等，所以可以用BFS求最短路。
时间复杂度分析：BFS的过程中每个点会遍历一次，每次遍历时需要枚举所有节点，判断是否存在边，总共需要判断 n2n2 次，假设单词长度是 LL，则每次判断时还需要 O(L)O(L) 的计算量，所以总时间复杂度是 O(n2L)O(n2L)。
BFS第一次收到的路径肯定是最短的,可以利用这个性质来解题
AC 代码
class Solution {
public boolean check(String s1,String s2){
int count = 0;
for (int i=0;i<s1.length();i++){
if (s1.charAt(i)!=s2.charAt(i)) count++;
}
return count==1;
}
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Map<String,Integer> dist = new HashMap<>();
dist.put(beginWord,1);
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
while (!queue.isEmpty()){
String str = queue.poll();
if (str .equals(endWord)) return dist.get(str);
for (int i =0;i<wordList.size();i++){
String word = wordList.get(i);
if (check(str,word)&& dist.get(word)==null){
dist.put(word,dist.get(str)+1);
queue.add(word);
}
}
}
return 0;
}
}
