120. Word Ladder （Self， WA）

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Thinking:
分为

1. 记录transformation的过程（记录如何变化的）
1. helper function 用来判断是否还剩一步就能变化成功，即与目标单词之差一个letter 
2. dfs
3. 如果在一次dfs中已经变化过那就可以从set去除了
2. 比较得到最短的tranformation
1. 设立rst为Integer.MAX_VALUE;

Leetcode discussion

1. It’s much faster than one-end search indeed as explained in wiki.
2. BFS isn’t equivalent to Queue. Sometimes Set is more accurate representation for nodes of level. (also handy since we need to check if we meet from two ends)
3. It’s safe to share a visited set for both ends since if they meet same string it terminates early. (vis is useful since we cannot remove word from dict due to bidirectional search)
4. It seems like if(set.add()) is a little slower than if(!contains()) then add() but it’s more concise.

 unsolved:
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Set<String> reached = new HashSet<String>();
        reached.add(beginWord);
        wordDict.add(endWord);
        int distance = 1;
        while (!reached.contains(endWord)) {
            Set<String> toAdd = new HashSet<String>();
            for (String each : reached) {
                for (int i = 0; i < each.length(); i++) {
                    char[] chars = each.toCharArray();
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        chars[i] = ch;
                        String word = new String(chars);
                        if (wordDict.contains(word)) {
                            toAdd.add(word);
                            wordDict.remove(word);
                        }
                    }
                }
            }
            distance++;
            if (toAdd.size() == 0) return 0;
            reached = toAdd;
        }
        return distance;