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"]

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

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

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