127. 单词接龙

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

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

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

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<String>();
        Set<String> set = new HashSet<String>();
        queue.offer(beginWord);
        set.add(beginWord);
        int res = 1;
        while (!queue.isEmpty()) {
            ++res;
            int size = queue.size();
            while (size > 0) {
                String cur = queue.poll();
                --size;
                for (String wd : wordList) {
                    if (check(wd, cur) && !set.contains(wd)) {
                        if (wd.equals(endWord)) {
                            return res;
                        }
                        queue.add(wd);
                        set.add(wd);
                    }
                }
            }
        }
        return 0;
    }

    private boolean check(String s1, String s2) {
        int diff = 0;
        for (int i = 0; i < s1.length(); ++i) {
            if (s1.charAt(i) != s2.charAt(i)) {
                ++diff;
                if (diff > 1) {
                    break;
                }
            }
        }
        return diff == 1;
    }
}