1. Word Ladder https://leetcode.com/problems/word-ladder/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 transformed word must exist in the word list. Note that beginWord is not a transformed word. For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
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. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same.

解题：给定一个起始词，一个结束词和一个词典，要求找到一条从起始到结束的路径，条件为每次只能换一个字母。这题用到是two end bfs，从两头出发，直到到达同一个词，途中记录path length。

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        // edge case，当两个词相同
        if (beginWord.equals(endWord)) {
            return 1;
        }
        //用两个set
        Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();

        //len记录path 长度
        int len = 1;
        int strLen = beginWord.length();
        HashSet<String> visited = new HashSet<String>();

        beginSet.add(beginWord);
        endSet.add(endWord);
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
                //这里当起始set大于终止set，调换一下，处理终止set
            if (beginSet.size() > endSet.size()) {
                Set<String> set = beginSet;
                beginSet = endSet;
                endSet = set;
            }

            Set<String> temp = new HashSet<String>();
            //起始set里面每一个词，我们把每一位的字母从［a－z］替换，组成新词
            for (String word : beginSet) {
                char[] chs = word.toCharArray();
                for (int i = 0; i < chs.length; i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        char old = chs[i];
                        chs[i] = c;
                        String target = String.valueOf(chs);
                        //看是否在终止set里面，如果是，说明我们找到了一条path
                        if (endSet.contains(target)) {
                            return len + 1;
                        }
                        //把新词加入visited 和 temp set    
                        if (!visited.contains(target) && wordList.contains(target)) {
                            temp.add(target);
                            visited.add(target);
                        }
                        //记得把原词放回去
                        chs[i] = old; 
                    }
                }
            }
            //然后把跟新beginSet为其距离为1的set
            beginSet = temp;
            len++;
        }

        return 0;
    }
}