LeetCode127. 单词接龙

语言：Java
算法：BFS

AC代码：

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int res = 0;
        Queue<String> queue = new LinkedList<>();
        Set<String> set = new HashSet<>();
        set.addAll(wordList);

        if (!set.contains(endWord)) {
            return 0;
        }

        queue.offer(beginWord);

        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;

            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                /**
                 * 将队列中的字符串取出，然后把这个字符串转化成字符数组，
                 * 将数组的每一个元素都用‘a’到‘z’去替换，然后判断这个元
                 * 素是否在set中存在，若存在，则将此字符串入队，并从set
                 * 中删除该字符串。
                 */
                for (int j = 0; j < str.length(); j++) {
                    char[] chars = str.toCharArray(); //将字符串转换成数组，方便后面的操作

                    for (char k = 'a'; k <= 'z'; k++) {
                        chars[j] = k;
                        String newStr = new String(chars);

                        if (newStr.equals(endWord)) {
                            return res + 1;
                        }

                        if (set.contains(newStr)) {
                            queue.offer(newStr);
                            set.remove(newStr);
                        }
                    }
                }
            }
        }
        return 0;
    }
}