数据结构和算法【81】单词接龙（华为OD笔试题目）

https://leetcode.cn/problems/word-ladder/solutions/276923/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you-2/

public class CodingDemo_03 {

    /**
     * 单词接龙
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //1，将给定单词列表转换为set，方便后续查找
        Set<String> wordSet = new HashSet<>(wordList);

        //因为题目要求 beginword 不在给定单词列表，这里我们删除可能存在的情况
        wordSet.remove(beginWord);

        //如果给定单词列表不包含 endword，肯定无法转换
        if (!wordSet.contains(endWord)){
            return 0;
        }

        //2，采用广度优先遍历，判断哪些可以满足一个字符替换
        //并同时记录哪些单词被访问过
        Deque<String> queue = new LinkedList<>();
        queue.addLast(beginWord);
        Set<String> visited = new HashSet<>();


        //开始遍历
        int step = 1; //记录转换次数
        while (!queue.isEmpty()){
            int curSize = queue.size();

            //广度遍历
            for (int i = 0; i < curSize; i++) {
                //弹出当前单词
                String curWord = queue.pollFirst();
                //判断当前单词，是否可以只变化一个字符，即可转换为 endWord
                //如果可以，则直接返回记录步数 step
                if (changeOneWordToEnd(wordSet, queue, visited,endWord, curWord)){
                    return step + 1;
                }
            }

            step++;//转换步数增加
        }
        return 0;
    }


    private boolean changeOneWordToEnd(Set<String> wordSet, Deque<String> queue,
                                       Set<String> visited, String endWord, String curWord){
        //1，因为要判断当前单词curWord，
        //只变化一个字符
        //所以先将字符串转换字符数组，方便字符替换
        final char[] ch = curWord.toCharArray();

        //2，尝试对每个字符进行 a-z 替换
        for (int i = 0; i < ch.length; i++) {
            //2.1 先把老字符记录下来
            char odd = ch[i];

            //2.2 尝试26种字符替换
            for (char j = 'a'; j <= 'z'; j++) {

                if (j == odd){
                    continue;
                }

                //2.3 替换
                ch[i] = j;

                //2.4 替换后的先单词
                String newWord = String.valueOf(ch);

                //2.5 判断是否存在
                if (wordSet.contains(newWord)){
                    if (newWord.equals(endWord)){
                        return true;
                    }

                    //如果之前没有被访问，则加入到队列，供下次遍历判断
                    //并标记为已经访问
                    if (!visited.contains(newWord)){
                        queue.offerLast(newWord);
                        visited.add(newWord);
                    }
                }
            }

            //还原
            ch[i] = odd;
        }
        return false;
    }
}