优化 最短单词路径 解法

[stanfordpeng]

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%90%9C%E7%B4%A2.md#3-%E6%9C%80%E7%9F%AD%E5%8D%95%E8%AF%8D%E8%B7%AF%E5%BE%84 最短单词路径这道题并不需要显式建图，完全可以继续使用BFS来搜索，只不过记得删除已经找到的元素，就可以减少复杂度了。 经过测试这个方法时间复杂度大大减小，并且代码更为直观简单：

class Solution {
    int length = 0;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)){
            return 0;
        }
        length = beginWord.length();
        
        Queue<String> que = new LinkedList<>();
        que.add(beginWord);
        int res = 0;
        while(!que.isEmpty())
        {
            int size = que.size();
            res ++;
            for(int j = 0;j < size;j++){
                String cur = que.remove();
                Iterator i = wordList.iterator();
                while(i.hasNext()){
                    String next = (String) i.next();

                    if(judge(next,cur)){
                        if(next.equals(endWord)){
                            return res+1;
                        }
                        que.add(next);
                        i.remove();
                    }
                }
            }
        }
        return 0;
        
    }
    
    boolean judge(String str1, String str2){
        //boolean res = true;
        int count = 0;
        for(int i = 0;i< length;i++){
            if(str1.charAt(i) != str2.charAt(i)){
                count++;
            }
            if(count>1) return false;
        }
        return true;
    }
    

}