赞
踩
给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列,返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出: 5
解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: 0
解释: endWord “cog” 不在字典中,所以无法进行转换。
题目可以转换为如下问题: 每个字符串可以看成是图中的节点,如果两个单词之间差一个字母,那么这两个节点是有一条边的,所以本题是求无向图起点到终点的最短路径。
最短路径可以用bfs算出。
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { if (beginWord.equals(endWord)) { return 1; } int cnt = 1; HashSet<String> set = new HashSet<>(wordList); if (!set.contains(endWord)) { return 0; } HashSet<String> visited = new HashSet<>(); Queue<String> queue = new LinkedList<>(); queue.add(beginWord); visited.add(beginWord); //System.out.println(visited); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String word = queue.poll(); // 寻找word只变一个字母可以变成的下一个单词,把这个单词加入队列 char[] wordArr = word.toCharArray(); for (int j = 0; j < word.length(); j++) { char tmp = wordArr[j]; for (char k = 'a'; k <= 'z'; k++) { wordArr[j] = k; String check = new String(wordArr); if (visited.contains(check)) { // 已经访问过,不能再访问 //System.out.println(check+" visited"); continue; } if (!set.contains(check)) { // wordList里面没有,说明遍历不到 //System.out.println(check+" doesn't exist"); continue; } if (check.equals(endWord)) { // 访问到了终点 //System.out.println("get end"); return cnt + 1; } //System.out.println("cnt = "+cnt+" word = "+word+" check = "+check); visited.add(check); queue.add(check); } wordArr[j] = tmp; } } //System.out.println(visited); cnt++; } // 如果bfs无法到达终点,会运行到这里 // System.out.println("cannot arrive"); return 0; } }
借助liweiwie的这张图理解一下双向bfs:
原来遍历的节点时红色部分,双向bfs遍历只需要遍历蓝色的菱形部分。
public int ladderLength(String beginWord, String endWord, List<String> wordList) { if (beginWord.equals(endWord)) { return 1; } int cnt = 1; HashSet<String> set = new HashSet<>(wordList); if (!set.contains(endWord)) { return 0; } HashSet<String> visited = new HashSet<>(); HashSet<String> beginVisited = new HashSet<>();// 从begin开始bfs的节点 HashSet<String> endVisited = new HashSet<>();// 从end开始bfs的节点 beginVisited.add(beginWord); endVisited.add(endWord); visited.add(beginWord); visited.add(endWord); while (!beginVisited.isEmpty() && !endVisited.isEmpty()) { // 每次bfs都选用节点数量小的,可以加快速度 if (beginVisited.size() > endVisited.size()) { HashSet<String> tmp = beginVisited; beginVisited = endVisited; endVisited = tmp; } HashSet<String> next = new HashSet<>(); for (String word : beginVisited) { // 同上一个方法,依次对每个位置的26个字母尝试 char[] wordArr = word.toCharArray(); for (int j = 0; j < wordArr.length; j++) { char tmp = wordArr[j]; for (char k = 'a'; k <= 'z'; k++) { wordArr[j] = k; String check = new String(wordArr); if (!set.contains(check)) { continue; } // 如果遍历到另外一个set里面的节点,说明重合了 if (endVisited.contains(check)) { return cnt + 1; } if (!visited.contains(check)){ next.add(check); visited.add(check); } } wordArr[j] = tmp; } } beginVisited = next; cnt++; } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。