讨论/《广度优先搜索》 - 例题:单词接龙/
《广度优先搜索》 - 例题:单词接龙

图的想法解决

    int length;
    int charLength;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        wordList.remove(endWord);
        wordList.add(beginWord);
        wordList.add(endWord);
        List<char[]> chars = wordList.stream().map(String::toCharArray).collect(Collectors.toList());
        this.length = chars.size();
        this.charLength = beginWord.length();
        ArrayList<Integer>[] arr = new ArrayList[length];
        for (int i = 0; i < length; i++) {
            arr[i] = new ArrayList<>();
        }
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (canWrite(chars.get(i), chars.get(j))) {
                    arr[i].add(j);
                    arr[j].add(i);
                }
            }
        }
        int end = length - 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(length - 2);

        int step = 0;
        Set<Integer> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            step++;
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                Integer curr = queue.poll();
                visited.add(curr);
                if (curr == end) {
                    return step;
                } else {
                    for (Integer start : arr[curr]) {
                        if (!visited.contains(start)) {
                            queue.offer(start);
                        }
                    }
                }
            }
        }
        return 0;
    }

    /**
     * 计算编辑距离=1的
     */
    public boolean canWrite(char[] from, char[] to) {
        int result = 0;
        for (int i = 0; i < charLength; i++) {
            if (from[i] != to[i]) {
                result++;
            }
        }
        return result == 1;
    }