LeetCode 127. Word Ladder BFS

题目描述
给定两个单词 (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;
 }
}