题解 | #牛群最短移动序列#

知识点

哈希，遍历

解题思路

使用队列和set，将头字符串放进队列中，将所有字符串数组放进set中。

从队列中取出字符串，遍历字符串中每一个字符，替换成其他字符，如果在set中含有，则将新的字符串再次入队。没遍历完一次队列中的全部字符串，level就加一，找到最终字符串就返回level+1；

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param beginWord string字符串
     * @param endWord string字符串
     * @param wordList string字符串一维数组
     * @return int整型
     */
    public int ladderLength (String beginWord, String endWord, String[] wordList) {
        // write code here
        //将单词数组放进set中
        Set<String> wordSet = new HashSet<>(Arrays.asList(wordList));
        //set中没有最终单词直接false
        if (!wordSet.contains(endWord)) {
            return 0;
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int level = 0; //最终答案层级
        while (!queue.isEmpty()) {
            //要先将size放到变量里，不然变动队列size会改变
            int size = queue.size();
            level++;
            //遍历队列
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                char[] arr = word.toCharArray();
                //遍历取出的字符串
                for (int j = 0; j < arr.length; j++) {
                    char originalChar = arr[j];
                    //遍历26个字母
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (ch == originalChar) {
                            continue;
                        }
                        arr[j] = ch;
                        //组合成新的字符串
                        String newWord = new String(arr);
                        if (newWord.equals(endWord)) {
                            return level + 1;
                        }
                        //set中含有新字符串入队并移除set中对应字符串
                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord);
                        }
                    }
                    arr[j] = originalChar;
                }
            }
        }
        return 0;
    }
}