Description

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:

Only one letter can be changed at a time 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. Hide Company Tags

Hint

two-end BFS

Train of Thought

traverse the path simultaneously from start node and end node, and merge in the middle the speed will increase (logN/2)^2 times compared with one-end method

Code

     public int ladderLength(String beginWord, String endWord, Set<String> wordList) {

               Set<String> start = new HashSet<String>();
               Set<String> end = new HashSet<String>();

               start.add(beginWord);
               end.add(endWord);
               //start and end words must be add to original list
               wordList.add(beginWord);
               wordList.add(endWord);


               Set<String> cur = new HashSet<String>();
               Set<String> oppo = new HashSet<String>();
               Set<String> visited = new HashSet<>();
               Set<String> tmp = new HashSet<>();

               int depth = 0;
               while (!start.isEmpty() && !end.isEmpty()){
                      if (start.size() > end.size()){
                          cur = end;
                          oppo = start;
                      } else {
                          cur = start;
                          oppo = end;
                      }
                      depth++;
                      tmp.clear();
                      for (String word : cur){
                           if (oppo.contains(word)){
                               return depth;
                           }
                           visited.add(word);
                           for (String s : getChildren(word, wordList)){
                                if (!visited.contains(s)){
                                    tmp.add(s);
                                }
                           }
                      }
                      cur.clear();
                      cur.addAll(tmp);
               }
               return 0;
        }

        private Set<String> getChildren(String word, Set<String> wordList){
                Set<String> children = new HashSet<String>();
                char[] strs = word.toCharArray();
                for (int i = 0; i < strs.length; i++){
                     char tmp = strs[i];
                     for (char replace = 'a'; replace <= 'z'; replace++){
                          strs[i] = replace;
                          String s = new String(strs);
                          if (wordList.contains(s)){
                              children.add(s);
                          }
                     }
                     strs[i] = tmp;
                }
                return children;
        }
    }

Complexity