LeetCode OJ

我觉得这道题比较难，主要是因为对于我来说：

1. 我没有把这个问题联想到树的宽度遍历（即便没有考虑树的宽度遍历，也是可以做的，但是我一开始实现的代码却是深度遍历，后来发现树的BFS一般使用queue实现的，貌似没有递归的方法？？）

2. 即使在意识到用BFS，却还有一个陷阱：我是对字典进行了BFS，这个说实话，代码长，还TLE；

后来参考了前辈的代码，采用对26个单词进行枚举，才解决了这个问题。

下面是AC代码：

/**
     * Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, 
     * BFS && 26 characters
     * @param start
     * @param end
     * @param dict
     * @return
     */
    public int ladderLength(String start, String end, HashSet<String> dict){
        if(start.equals(end))
            return 2;
        //for BFS 
        LinkedList<String> queue = new LinkedList<String>();
        //store the words that have visited and in the dict
        HashSet<String> visited = new HashSet<String>();
        //the level information for every word
        LinkedList<Integer> level = new LinkedList<Integer>();
        queue.offer(start);
        level.offer(1);
        while(!queue.isEmpty()){
            String interW = queue.poll();
            int le = level.poll();
            
            //for every character in the word
            for(int i=0;i<interW.length();i++){
                
                char[] words = interW.toCharArray();
                char o = words[i];//the original word
                for(char c='a';c<='z';c++)
                {
                    if(c!=o){
                        //subsitude by another char
                        words[i] = c;    
                        String changed = new String(words);
                        if(changed.equals(end))
                            return le+1;
                        if((!visited.contains(changed)) && dict.contains(changed)){
                            visited.add(changed);
                            queue.offer(changed);
                            level.offer(le+1);
                        }
                    }
                }
                
            }
        }
        return 0;
    }