Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

return its length 5.

Note:

• • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

解题思路：

　　BFS, 类似于图的遍历， 将start一步内可以到达的单词加入到queue中，并将相应的长度放入另一个queue中，每次poll 出一个单词，看是否是目标单词，如果是，则返回相应的长度。

对每个单词的每一位进行'a' - 'z' 的变化，看是否在 dict中，如果在，则说明该单词是转换路径中的一个。将该词从字典中删除。（表示已经访问过了）

public class Solution {    public int ladderLength(String start, String end, HashSet
     
       dict) {        int result = 0;                if(dict.size() == 0){            return result;         }                dict.add(start);        dict.add(end);                result = BFS(start, end, dict);                return result;            }            public int BFS(String start, String end, HashSet
      
        dict){        Queue
       
         words = new LinkedList
        
         ();        Queue
         
           lengths = new LinkedList
          
           (); words.add(start); lengths.add(1); while(!words.isEmpty()){ String word = words.poll(); int len = lengths.poll(); if(word.equals(end)){ return len; } for(int i = 0; i< word.length(); i++){ char[] arr = word.toCharArray(); for (char c = 'a'; c <= 'z'; c++) { if(arr[i] == c){ continue; } arr[i] = c; String str = String.valueOf(arr); if(dict.contains(str)){ words.add(str); lengths.add(len+1); dict.remove(str); } } } } return 0; } }