LC 127 Word Ladder(M)

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 intermediate word must exist in the word list.

Note:

• Return 0 if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

解体思路: BFS

这道题的解题方法就是BFS，而且有单向BFS和双向BFS两种

单向BFS：从起始的Word加入到队列当中，每次从队列中取出一个词，并加入词表中和他只差别一位且未使用的词 重复上述过程，直到当前取出的词可以一位变换到结束的词

双向BFS：交替开始词串，和结尾词串 队列。

public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    Set<String> beginSet = new HashSet<String>(); 
    Set<String> endSet = new HashSet<String>();
    int len = 1;
    int strLen = beginWord.length();
    HashSet<String> visited = new HashSet<String>();

    beginSet.add(beginWord);
    endSet.add(endWord);
    while (!beginSet.isEmpty() && !endSet.isEmpty()) {
        //交换 让beginSet 始终是小数组
        if (beginSet.size() > endSet.size()) {
            Set<String> set = beginSet;
            beginSet = endSet;
            endSet = set;
        }

        Set<String> temp = new HashSet<String>();
        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);

                    if (endSet.contains(target)) {
                        return len + 1;
                    }

                    if (!visited.contains(target) && wordList.contains(target)) {
                        temp.add(target);
                        visited.add(target);
                    }
                    chs[i] = old;
                }
            }
        }

        beginSet = temp;
        len++;
    }    
    return 0;
}