Word Ladder 127

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.

Hint

DFS

Method

Generally, we transfer from start to the end. each time we loop each word in start set to find next transformation that in the wordlist to extend the transformation until we meet the end word.

so we can do

Time & Space

Code

public class Solution {
    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);
           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;
    }
}