题解 | 牛群最短移动序列

1. HashSet
2. BFS

import java.util.*;


public class Solution {
    public int ladderLength (String beginWord, String endWord, String[] wordList) {
        final Set<String> wordSet = new HashSet<>(Arrays.asList(wordList));
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        Deque<String> q = new ArrayDeque<>();
        q.addLast(beginWord);
        int level = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            ++level;
            for (int i = 0; i < size; ++i) {
                final String word = q.removeFirst();
                char[] wordCharArray = word.toCharArray();
                for (int j = 0; j < wordCharArray.length; j++) {
                    final char originChar = wordCharArray[j];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (ch == originChar) {
                            continue;
                        }
                        wordCharArray[j] = ch;
                        final String newWord = new String(wordCharArray);
                        if (wordSet.contains(newWord)) {
                            if (newWord.equals(endWord)) {
                                return level;
                            }
                            q.addLast(newWord);
                            wordSet.remove(newWord);
                        }
                    }
                    wordCharArray[j] = originChar;
                }
            }
        }
        return 0;
    }
}