127_ladderLength.txt

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList){
        //BFS广度优先搜素
        //如果字典中不存在目标单词直接返回0
        if(!wordList.contains(endWord))
            return 0;
        Set<String> visited = new HashSet<>();//记录访问过的元素
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        visited.add(beginWord);
        int count = 0;
        while(queue.size()>0){
            int size = queue.size();
            count++;
            for(int i = 0;i<size;i++){
                String start = queue.poll();
                for(String s:wordList){
                    //跳过已经访问过的元素
                    if(visited.contains(s))
                        continue;
                    //不能正常转换的也跳过
                    if(!canconvert(start,s))
                        continue;
                    //如果此时s已经是endword说明转换已经完成了可以返回
                    if(s.equals(endWord))
                        return count+1;
                    queue.offer(s);
                    visited.add(s);
                }
            }
        }
        return 0;
    }
    //判断两个字符串能否按照规则转换的方法
    public boolean canconvert(String s1,String s2){
        //长度不等直接返回
        if(s1.length()!=s2.length())
            return false;
        int count = 0;//记录字符不同的个数
        for(int i = 0;i<s1.length();i++){
            if(s1.charAt(i)!=s2.charAt(i))
                count++;
            if(count>1)
                return false;
        }
        return count==1;//只有一个字符不同时才返回true
    }
}