public class WordLadder {
　　//把start通过dict内的字符串转换成end需要多少步  一次只能转换一个char  方案：广度优先算法
    public static void main(String[] args) {
        String start = "hit";
        String end = "cog";
        Set<String> dict = new HashSet<>();
        dict.add("hot");
        dict.add("dot");
        dict.add("dog");
        dict.add("lot");
        dict.add("log");
        System.out.println(getStep(start,end,dict));

    }

    public static int getStep(String start, String end, Set<String> dict){
        if(dict==null||dict.size()==0){
            return 0;
        }
        dict.add(end);
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        Set<String> duplicate = new HashSet<>();
        int step = 1;
        while (!queue.isEmpty()){
            step++;
            int size = queue.size();
            for(int i=0;i<size;i++){
                String word = queue.poll();
                List<String> nextList = getNextList(word,dict);
                for(String s:nextList){
                    if(duplicate.contains(s)){
                        continue;
                    }
                    if(s.equals(end)){
                        return step;
                    }
                    duplicate.add(s);
                    queue.offer(s);
                }
            }
        }
        return -1;
    }

    private static List<String> getNextList(String word, Set<String> dict) {
        List<String> nextList = new ArrayList<>();
        for(char i=‘a‘;i<‘z‘;i++){
            for(int j=0;j<word.length();j++){
                String next = getWord(word,i,j);
                if(dict.contains(next)){
                    nextList.add(next);
                }
            }
        }
        return nextList;
    }

    private static String getWord(String word, char i, int j) {
        char[] array = word.toCharArray();
        array[j]=i;
        return new String(array);
    }
}

单词梯问题