> 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/bfs/word-ladder.md).

# Word Ladder 07/30

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

* Return 0 if there is no such transformation sequence.
* All words have the same length.
* All words contain only lowercase alphabetic characters.

#### Example

Given:\
start = `"hit"`\
end = `"cog"`\
dict = `["hot","dot","dog","lot","log"]`<br>

As one shortest transformation is `"hit" -> "hot" -> "dot" -> "dog" -> "cog"`,\
return its length `5`.

经典的BFS问题，题中没有交代end是否在辞典里，所以要往词典里加一次,findNext 时间复杂度是O(N\*M),M是 单词长度，N是词典的size,

```java
public class Solution {
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: An integer
     */
   public int ladderLength(String start, String end, Set<String> dict) {
            if(start.equals(end)){
                return 1;
            } 
            
            if(dict.size() == 0){
                return 0;
            }
            
            Queue<String> queue = new LinkedList<>();
            dict.add(end);
            queue.offer(start);
            int change = 0;
            while(!queue.isEmpty()){
                int size = queue.size();
                change++;
               
                for (int i = 0; i < size ;i++ ){
                     String word = queue.poll();
                    if(word.equals(end)){
                        return change;
                    }
                    
                    List<String> list = findNext(word,dict);
                    for(String s : list){
                        if(s.equals(end)){
                            return change+1;
                        }
                        queue.offer(s);
                    }
                } 
                
                
                
            }
            
            return change;
            
    }
    
    public List<String> findNext(String s, Set<String> dict){
        int diff = 0;
        
        List<String> res = new ArrayList<>();
        
        for(String word : dict){
            for(int i = 0; i < s.length();i++){
                if(s.charAt(i) == word.charAt(i)){
                    continue;
                }
                diff++;
            }
            
            if(diff == 1){
                res.add(word);
                
            }
            diff= 0;
        }
        dict.removeAll(res); 
        return res;
    }
    
   
   
}
```