Word Ladder

Medium

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.

Note:

• Return 0 if there is no such transformation 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.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Analysis

这道题很经典，巧妙之处在于转化问题：wordList中的word相当于图中的节点，是否存在边连接节点呢？就在于改变word中的一个字符时能否找到另一个节点，即图中的两个word节点之间否有边，取决于两个word之间是否只相差一个字符串。beginWord相当于起点，endWord相当于终点。Word Ladder的问题本质其实就是寻找起点到终点的最短路径。这样，用BFS就可以解决。

改变字符串中的字符的两种方法：

StringBuilder()

StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
    sb.setCharAt(j, ch);
    String newWord = sb.toString();
    ...
}

toCharArray()

char[] chs = s.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++ ) {
    chs[i] = ch;
    String newStr = new String(chs);
    ...
}

The intuition:

BFS -- Altering one character at a time for beginWord, and see if it's in the wordList, if yes, then add to the toSearch list; for the word in toSearch list, do the same: altering one character at a time, see if it's in wordList, so on and so forth.

Note: to avoid cyclical search, we need to remove the "searched" word from the wordList

Optimization: using two end BFS

Solution

BFS (using set)- (133ms 43.15%)

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // wordSet storing non-visited words
        Set<String> wordSet = new HashSet<String> (wordList);
        // reachSet storing visted words
        Set<String> reachSet = new HashSet<String>();
        if (beginWord == null || endWord == null || !wordSet.contains(endWord)) return 0;

        reachSet.add(beginWord);
        int step = 1;

        while (!reachSet.contains(endWord)) {
            HashSet<String> temp = new HashSet<String>();
            for (String s : reachSet) {
                for (int i = 0; i < s.length(); i++) {
                    char[] chs = s.toCharArray();
                    for (char ch = 'a'; ch <= 'z'; ch++ ) {
                        chs[i] = ch;
                        String nStr = new String(chs);
                        if (wordSet.contains(nStr)) {
                            if (endWord.equals(nStr)) return step + 1;
                            // add new valid word to the temp set
                            temp.add(nStr);
                            wordSet.remove(nStr);
                        }
                    }
                }
            }
            step++;
            if (temp.size() == 0) return 0;
            reachSet = temp;
        }
        return step;
    }
}

A more "traditional" BFS using Queue (63 ms, faster than 78.37%)

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) {
            return 0;
        }

        Deque<String> q = new ArrayDeque<>();
        q.offer(beginWord);
        int step = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String word = q.poll();
                int wordLength = word.length();
                for (int j = 0; j < wordLength; j++) {
                    StringBuilder sb = new StringBuilder(word);
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        sb.setCharAt(j, ch);
                        String newWord = sb.toString();
                        if (newWord.equals(endWord)) {
                            return step + 1;
                        }
                        if (set.contains(newWord)) {
                            q.offer(newWord);
                            set.remove(newWord); // to avoid infinited loop
                        }
                    }
                }
            }
            step++;
        }
        return 0;
    }
}

Two-End BFS (15 ms, faster than 99.01%)

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
       Set<String> set = new HashSet<>();

        for(String str : wordList) set.add(str);

        if (beginWord == null || endWord == null || !set.contains(endWord)) return 0;

        Set<String> beginSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        beginSet.add(beginWord);
        endSet.add(endWord);
        set.remove(endWord);
        int step = 1;

        while(!beginSet.isEmpty() && !endSet.isEmpty()) {
            Set<String> next = new HashSet<>();
            if (beginSet.size() > endSet.size()) {
                Set<String> temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            }

            for(String str : beginSet) {
                char[] word = str.toCharArray();
                for(int i = 0; i < word.length; i++) {
                    char old_c = word[i];

                    for(char c = 'a'; c <= 'z'; c++) {
                        word[i] = c;
                        String cur = new String(word);
                        if (endSet.contains(cur)) return step+1;
                        if (set.contains(cur)) {
                            next.add(cur);
                            set.remove(cur);
                        }
                    }
                    word[i] = old_c;
                }
            }
            beginSet = next;
            step++;
        }
    return 0;
    }
}

Reference

https://leetcode.com/articles/word-ladder/

https://leetcode.com/problems/word-ladder/discuss/40704/Java-Solution-using-BFS-with-explanation/175121