Word Ladder

上次写的：https://shuati.gitbook.io/crack-lintcode/~/edit/drafts/-LMiAXskoui1zxTa8eLA/bfs/word-ladder

leetcode 版本 不保证end 一定在list里

注意：每次while内循环queue的size 次，一次就是一层，在这个地方统计次数

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        
        
        if(!wordList.contains(endWord)){
            return 0;
        }
        
        Queue<String> queue = new LinkedList<>();
        Set<String> set = new HashSet<>();
        
        queue.offer(beginWord);
        set.add(beginWord);
        int count = 0;
        while(!queue.isEmpty()){
            
            int size = queue.size();
                count++;
            for(int i = 0; i < size;i++){
                String word = queue.poll();
                if(word.equals(endWord))
                    return count;
                 List<String> nextWords = getNextWordsList(wordList,word);
            for(String nw : nextWords){
               
                if(nw == endWord){
                    return count+1;
                }
                if(!set.contains(nw)){
                    set.add(nw);
                    queue.offer(nw);
                }
                
            }
                
            }
        }
        
        return 0;
    }
    
    public List<String> getNextWordsList(List<String> wordList, String word){
        List<String> res = new ArrayList<>();
        
        
        
        for(String w : wordList){
            int diff = 0;
            for(int i = 0; i < w.length();i++){
                if(w.charAt(i) != word.charAt(i))
                    diff++;
            }
            
            if(diff == 1){
                res.add(w);
            }
        }
        wordList.removeAll(res);
        return res;
    }
    
    
}

当词典数量非常大的时候，遍历26个字母来寻找下一组单词，比较好，

首先, 令L为单词长度, N为单词数目, 那么Set.contain()的平均复杂度一般是O(L). 所以, jiuzhang的算法的复杂度是26 * O(L) * O(L) = O(26L^2). 而你的算法则是O(LN). 至于哪种算法更优, 要看dict的L和N哪个更大. 实际的字典一般都满足N >> L,

用这种方法，词典要放在hashset里，因为list contains 是on， set 是o1

对于每个节点构图需要的时间复杂度是O(26*L)，BFS不重复地至多走过n个节点，故算法复杂度O(26*L*n)

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        
        Set<String> dic = new HashSet<>();
        
        
        
        for(String word : wordList){
            dic.add(word);
        }
        
        if(!dic.contains(endWord)){
            return 0;
        }
        
        Queue<String> queue = new LinkedList<>();
        Set<String> set = new HashSet<>();
        
        queue.offer(beginWord);
        set.add(beginWord);
        int count = 0;
        while(!queue.isEmpty()){
            
            int size = queue.size();
            count++;
            for(int i = 0; i < size;i++){
                String word = queue.poll();
                
                if(word.equals(endWord)) return count;
                
                List<String> nextWords = getNextWordsList(dic,word);
                
                for(String nw : nextWords){
                    
                    
                    if(nw == endWord){
                        return count+1;
                    }
                    if(!set.contains(nw)){
                        set.add(nw);
                        queue.offer(nw);
                    }
                
                }
                
            }
        }
        
        return 0;
    }
    
     private String replace(String s, int index, char c) {
        char[] chars = s.toCharArray();
        chars[index] = c;
        return new String(chars);
    }
    
    public List<String> getNextWordsList(Set<String> wordList, String word){
         List<String> nextWords = new ArrayList<String>();
        
        for (char c = 'a'; c <= 'z'; c++) {
           
            for (int i = 0; i < word.length(); i++) {
                if (c == word.charAt(i)) {
                    continue;
                }
                
                String nextWord = replace(word, i, c);
                
                if (wordList.contains(nextWord)) {
                    nextWords.add(nextWord);
                }
            }
        }
        return nextWords;
    }
    
    
}