package code; /* * 127. Word Ladder * 题意：给定开始字符串，结束字符串，和一个字符串数组，每次替换字符串中的一个字符，问最少几个步骤变为终止字符串 * 难度：Medium * 分类：Breadth-first Search * 思路：bfs, 利用双向bfs可以加快搜索https://leetcode.com/problems/word-ladder/discuss/40711/Two-end-BFS-in-Java-31ms. * Tips：拓扑排序，很经典的BFS，好好看看 * lc207 */ import java.util.ArrayDeque; import java.util.List; import java.util.Queue; public class lc127 { public int ladderLength(String beginWord, String endWord, List wordList) { if(!wordList.contains(endWord)) return 0; Queue qu = new ArrayDeque(); //用一个Queue和int size类似树的层次遍历，和两个hashset效果一样 qu.add(beginWord); int level = 2; while(!qu.isEmpty()){ int size = qu.size(); for (int i = 0; i < size ; i++) { char[] curr_str = qu.remove().toCharArray(); System.out.println(String.valueOf(curr_str)); for (int j = 0; j < curr_str.length ; j++) { char ch = curr_str[j]; for (char k = 'a'; k <='z' ; k++) { //如果每次比较两个字符串是否差一位，时间复杂度太大，所以直接替换一个字符 curr_str[j] = k; if(String.valueOf(curr_str).equals(endWord)) return level; if(wordList.contains(String.valueOf(curr_str))){ wordList.remove(String.valueOf(curr_str)); //这要remove qu.add(String.valueOf(curr_str)); } } curr_str[j] = ch; } } level++; } return 0; } }