Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

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

For example,

Given:

beginWord = "hit"

endWord = "cog"

wordList = ["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.
    1 public class Solution { 2     public int ladderLength(String beginWord, String endWord, Set
             
               wordList) { 3         if (wordList.size () == 0) { 4             return 0; 5         } 6         wordList.add(beginWord); 7         wordList.add(endWord); 8         HashSet
              
                set = new HashSet<>(); 9         Queue
               
                 q = new LinkedList<>();10         set.add(beginWord);11         q.offer(beginWord);12         int length = 1;13         while (!q.isEmpty()) {14             ++length;15             int size = q.size();16             for (int i = 0; i < size; i++) {17                 String crt = q.poll();18                 for (String next : getNextWords(crt, wordList)) {19                     if (set.contains(next)) {20                         continue;21                     } 22                     if (next.equals(endWord)) {23                         return length;24                     } 25                     q.offer(next);26                     set.add(next);27                 }28             }29         }30         return 0;31     }32      private String replace(String s, int index, char c) {33         char[] chars = s.toCharArray();34         chars[index] = c;35         return new String(chars);36     }37     private ArrayList
                
                  getNextWords(String word, Set
                 
                   dict) {38         ArrayList
                  
                    nextWords = new ArrayList
                   
                    ();39 for (char c = 'a'; c <= 'z'; c++) {40 for (int i = 0; i < word.length(); i++) {41 if (c == word.charAt(i)) {42 continue;43 }44 String nextWord = replace(word, i, c);45 if (dict.contains(nextWord)) {46 nextWords.add(nextWord);47 }48 }49 }50 return nextWords;51 }52 53 }