Question:

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.

Thinking:

We can search the result from the start word. At every step, we change the every index of the start string and check if it’s in the WordList. If it’s in the range, then we add it to our nodes. Do it like a BFS search. Also in order to be more efficient, we can search also from the end word.

Solution:

public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    if (beginWord.equals(endWord))    return 1;
    Set<String> startSet = new HashSet<String>();
    Set<String> endSet =  new HashSet<String>();
    int res = 1;
    startSet.add(beginWord);
    endSet.add(endWord);
    while (!wordList.isEmpty() && !startSet.isEmpty() && !endSet.isEmpty()) {
        res++;
        Set<String> tempSet = new HashSet<String>();
        for (String nWord: startSet) {
            wordList.remove(nWord);
            for (String ele: check(nWord, wordList)) {
                if (endSet.contains(ele))    return res;
                tempSet.add(ele);
            }
        }
        startSet = tempSet;
        tempSet = new HashSet<String>();
        res++;
        for (String nWord: endSet) {
            wordList.remove(nWord);
            for (String ele: check(nWord, wordList)) {
                if (startSet.contains(ele))    return res;
                tempSet.add(ele);
            }
        }
        endSet = tempSet;
    }
    return 0;
}
private List<String> check(String word, Set<String> wordList) {
    List<String> res = new ArrayList<String>();
    int len = word.length();
    if (len == 1)    {
        res.addAll(wordList);
        return res;
    }
    for (int i = 0; i < len; i++) {
        char[] chs = word.toCharArray();
        for (char j = 'a'; j <= 'z'; j++) {
            chs[i] = j;
            String temp = String.valueOf(chs);
            if (wordList.contains(temp))    res.add(temp);              
        }
    }
    return res;
}