> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/linkedin/word-ladder.md).

# Word Ladder

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

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

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

```java
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)`

```java
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;
    }
    
    
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://shuati.gitbook.io/crack-lintcode/linkedin/word-ladder.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.