力扣 127 单词接龙

题意：给定一个字典和开始str，和结束str，每次换一个字母，问从开始str到结束str的最少转换次数

思路：

1. 用HashSet把字典加入其中
2. 用queue记录当前遍历到的字符，开始时把beginWord放进去
3. 每次从queue里pop出头节点，遍历pop出的str的每一位，并把每一位换成26个字母中的一个，重构字符串，并查看是否在字典中
4. 如果在就加入queue，并把加入的单词从字典删除，如果该单词是endWord那么返回遍历的层数
5. 没找到返回0

思想：BFS

复杂度：时间O（n)，空间O(n)

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> set = new HashSet();
        for(String str: wordList) {
            set.add(str);
        }
        
        Queue<String> q = new LinkedList();
        
        q.add(beginWord);
        
        int level = 1;
        int end = 1;
        int start = 0;
        int res = 1;
        while(!q.isEmpty()) {
            String temp = q.poll();
            start++;
            for(int i=0;i<temp.length();i++) {
                char[] arr = temp.toCharArray();
                char t = arr[i];
                for(int j=0;j<26;j++) {
                    char cur = (char)(j + 'a');
                    if(t != cur) {
                        arr[i] = cur;
                        String st = new String(arr);
                        if(set.contains(st)) {
                            if(endWord.equals(st)){
                                return res+1;
                            }
                            set.remove(st);
                            q.add(st);
                            end++;
                        }
                    }   
                }
            }
            if(start == level) {
                res++;
                level = end;
            }
        }
        return 0;
    }
}