127. 单词接龙
127. 单词接龙
这个跟昨天的题还是有点不一样的，这个如果按照昨天的方法，会超时，因为时间已经到了50000
题目：
题解：
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { //创建队列 Queue<String> queue = new LinkedList<>(); //将起始单词放入队列 queue.offer(beginWord); //用map来进行确认是否是有效访问位 //如果该单词在map中，证明已经访问过 Map<String, Integer> visted = new HashMap<>(); visted.put(beginWord, 1); //转换步数 int step = 0; //用来确认是否在字典中 Set<String> wordSet = new HashSet<>(wordList); while(queue.size()>0) { int size = queue.size(); step++; for(int i=0;i<size;i++) { //取出队列的单词 String t = queue.poll(); //看是否是endWord if(t.equals(endWord)) { return step; } for(int j=0;j<t.length();j++) { StringBuilder s = new StringBuilder(t); for(char c='a';c<='z';c++) { if(s.charAt(j)==c) { continue; } s.setCharAt(j,c); //如果字典中存在该单词，且该单词没有被访问过 if(wordSet.contains(s.toString())&&!visted.containsKey(s.toString())) { //加入队列中 queue.offer(s.toString()); //将t设置成有效访问位 visted.put(s.toString(), 1); } } } } } return 0; } }
