1、前言

2、思路

如果用 BFS 来做，需要知道怎样把这个过程抽象成一个图。模仿转盘锁的思路来做，其实思路是一样的。此题 case 抽象的图如图所示：

3、代码

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> words = new HashSet<>(wordList);
        if(!words.contains(endWord)){
            return 0;
        }

        words.remove(beginWord);

        HashSet<String> visited = new HashSet<>();
        List<String> queue = new ArrayList<>();

        queue.add(beginWord);
        visited.add(beginWord);
        int step = 1;
        while(!queue.isEmpty()){
            int size = queue.size();

            for(int i = 0; i < size; i++){
                String cur = queue.remove(0);
                char[] chars = cur.toCharArray();

                for(int j = 0; j < beginWord.length(); j++){

                    char originChar = chars[j];

                    for(char k = 'a'; k <= 'z'; k++){
                        if(k == originChar){
                            continue;
                        }

                        chars[j] = k;
                        String nextWord = new String(chars);

                        if(words.contains(nextWord)){
                            if(nextWord.equals(endWord)){
                                return step + 1;
                            }

                            if(!visited.contains(nextWord)){
                                visited.add(nextWord);
                                queue.add(nextWord);
                            }
                        }
                    }

                    chars[j] = originChar;
                }
            }

            step++;
        }

        return 0;
    }
}