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 transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]

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

return its length 5.

Note:

• Return 0 if there is no such transform
  • ation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

   

  UPDATE (2017/1/20):

  The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.
  package tecent;import java.util.HashSet;import java.util.Scanner;import java.util.Set;public class Main3 {        public static void main(String args[]){        Scanner sc = new Scanner(System.in);        String begin =sc.nextLine();        String end = sc.nextLine();        Set
         
           wordList = new HashSet<>();        String list = sc.nextLine();        String [] word = list.split(" ");        for(int i=0;i
          
            wordList) {            // if(!wordList.contains(beginWord)||!wordList.contains(endWord)) return 0;            Set
           
             beginSet = new HashSet
            
             (), endSet = new HashSet
             
              ();            int len = 1;            int strLen = beginWord.length();            HashSet
              
                visited = new HashSet
               
                (); beginSet.add(beginWord); endSet.add(endWord); while (!beginSet.isEmpty() && !endSet.isEmpty()) { if (beginSet.size() > endSet.size()) { Set
                
                  set = beginSet; beginSet = endSet; endSet = set; } Set
                 
                   temp = new HashSet
                  
                   (); for (String word : beginSet) { char[] chs = word.toCharArray(); for (int i = 0; i < chs.length; i++) { for (char c = 'a'; c <= 'z'; c++) { char old = chs[i]; chs[i] = c; String target = String.valueOf(chs); if (endSet.contains(target)) { return len + 1; } if (!visited.contains(target) && wordList.contains(target)) { temp.add(target); visited.add(target); } chs[i] = old; } } } beginSet = temp; len++; } return 0; } }