gold-17-22

给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。

编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。

示例 1:

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

输出:
["hit","hot","dot","lot","log","cog"]

示例 2:

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

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

//面试题 17.22. 单词转换
class Solution {
    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<String> list = new ArrayList<>();
        Set<String> set = new HashSet<>(wordList);
        if(!set.contains(endWord)) {
            return list;
        }
        Queue<List<String>> queue = new ArrayDeque<>();
        list.add(beginWord);
        queue.add(list);
        set.remove(beginWord);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                List<String> curPath = queue.poll();
                String curWord = curPath.get(curPath.size() - 1);
                for (int i = 0; i < curWord.length(); i++) {
                    char[] ch = curWord.toCharArray();
                    char temp = ch[i];
                    for (char j = 'a'; j <= 'z'; j++) {
                        if (j == temp) {
                            continue;
                        }
                        ch[i] = j;
                        String nextWord = new String(ch);
                        if (set.contains(nextWord)) {
                            List<String> newPath = new ArrayList<>(curPath);
                            newPath.add(nextWord);
                            set.remove(nextWord);
                            if (nextWord.equals(endWord)) {
                                return newPath;
                            } else {
                                queue.add(newPath);
                            }
                        }
                    }
                    ch[i] = temp;
                }
                size--;
            }
        }
        return new ArrayList<>();
    }
}