LeetCode - 127. Word Ladder 126 (BFS)

LeetCode - 127. Word Ladder & 126 (BFS)

• LeetCode - 127. Word Ladder
• LeetCode - 126. Word LadderII

LeetCode - 127. Word Ladder

题目链接

题目

解析

两种解法: 单向BFS和双向BFS(Bidrectional BFS)。

单向BFS:

• 首先将wordDict转换成Set集合(记为dict)，这样查找更快，不然会TLE；
• 每次尝试更改一个字符(a ~ z)，然后去判断是否这个在dict中，如果可以，加入队列；

第一版:

class Solution {private class State {public String word;public int step;public State(String word, int step) {this.word = word;this.step = step;}}public int ladderLength(String beginWord, String endWord, List<String> wordList) {HashSet<String> dict = new HashSet<>(wordList); // 将wordList转换成HashSet查找更快return bfs(new State(beginWord, 0), new State(endWord, 0), dict) + 1;}private int bfs(State begin, State end, Set<String> dict) {Queue<State> queue = new LinkedList<>();queue.add(begin);HashMap<String, Boolean> visMap = new HashMap<>();visMap.put(begin.word, true);while (!queue.isEmpty()) {State cur = queue.poll();if (cur.word.equals(end.word))return cur.step;for (int i = 0; i < cur.word.length(); i++) {StringBuilder sb = new StringBuilder(cur.word);for (char c = 'a'; c <= 'z'; c++) {if (cur.word.charAt(i) == c)continue;sb.setCharAt(i, c);if (visMap.get(sb.toString()) == null && dict.contains(sb.toString())) {visMap.put(sb.toString(), true);queue.add(new State(sb.toString(), cur.step + 1));}}}}return -1;}
}

第二版: 没有使用visMap，而是当一个字符串(节点)，已经被访问过了之后，就从dict中移除即可。

class Solution {private class State {public String word;public int step;public State(String word, int step) {this.word = word;this.step = step;}}public int ladderLength(String beginWord, String endWord, List<String> wordList) {HashSet<String> dict = new HashSet<>(wordList); // 将wordList转换成HashSet查找return bfs(new State(beginWord, 0), new State(endWord, 0), dict) + 1;}private int bfs(State begin, State end, Set<String> dict) {Queue<State> queue = new LinkedList<>();queue.add(begin);while (!queue.isEmpty()) {State cur = queue.poll();if (cur.word.equals(end.word))return cur.step;for (int i = 0; i < cur.word.length(); i++) {StringBuilder sb = new StringBuilder(cur.word);for (char c = 'a'; c <= 'z'; c++) {if (cur.word.charAt(i) == c)continue;sb.setCharAt(i, c);if (dict.contains(sb.toString())) {queue.add(new State(sb.toString(), cur.step + 1));dict.remove(sb.toString()); // 直接移除这个就好，不需要使用一个HashMap}}}}return -1;}
}

第三版: 将结构体去掉。

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {HashSet<String> dict = new HashSet<>(wordList);// start bfsQueue<String> queue = new LinkedList<>();queue.add(beginWord);int level = 0;// 层数while (!queue.isEmpty()) {level++;int qsize = queue.size(); // 一定要定义一个变量，不能在下面的循环中直接写queue.size(),因为会变化for(int size = 0; size < qsize; size++){ //当前这一层的节点的数目String cur = queue.poll();for (int i = 0; i < cur.length(); i++) {StringBuilder sb = new StringBuilder(cur);for (char c = 'a'; c <= 'z'; c++) {if (cur.charAt(i) == c)continue;sb.setCharAt(i, c);if (dict.contains(sb.toString())) {if(sb.toString().equals(endWord))return level + 1;queue.add(sb.toString());dict.remove(sb.toString());}}}}}return 0;}
}

双向BFS

• 用两个集合Set，分别从两边开始搜索(代码上是从一边，但是交换两个集合)；
• 这样的话，返回的条件就是当前扩展的节点如果在endSet中有就返回；

注意dict.removeAll(beginSet);这一样，是将beginSet原来的单词从dict中移除掉，而不能在循环中dict.remove(next);，因为可能会移除掉对面endSet中的元素，导致失败。

class Solution{public int ladderLength(String beginWord, String endWord, List<String> wordList) {HashSet<String> dict = new HashSet<>(wordList);if (!dict.contains(endWord))return 0;HashSet<String> beginSet = new HashSet<>();HashSet<String> endSet = new HashSet<>();beginSet.add(beginWord);endSet.add(endWord);int step = 0;while (!beginSet.isEmpty() && !endSet.isEmpty()) {++step;if (beginSet.size() > endSet.size()) {HashSet<String> hs = beginSet;beginSet = endSet;endSet = hs;}HashSet<String> nextSet = new HashSet<>();for (String cur : beginSet)  {char[] chs = cur.toCharArray();for (int i = 0; i < chs.length; i++) {char old = chs[i];for (char c = 'a'; c <= 'z'; c++) {chs[i] = c;String next = String.valueOf(chs);if (dict.contains(next)) {if (endSet.contains(next))return step + 1;nextSet.add(next);// dict.remove(next); //不能这样}}chs[i] = old;}}dict.removeAll(beginSet);beginSet = nextSet;}return 0;}
}

也可以将上面的方法改成递归:

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Set<String> beginSet = new HashSet<>();Set<String> endSet = new HashSet<>();beginSet.add(beginWord);endSet.add(endWord);Set<String> dict = new HashSet<>(wordList);if(!dict.contains(endWord)) return 0;return bfs(beginSet, endSet, dict, 0);}private int bfs(Set<String> beginSet, Set<String> endSet, Set<String> dict, int step){if(beginSet.isEmpty() || endSet.isEmpty()) return 0;step++;dict.removeAll(beginSet);Set<String> nextSet = new HashSet<>();for(String str : beginSet){char[] chs = str.toCharArray();for(int i = 0; i < chs.length; i++){char old = chs[i];for(char c = 'a'; c <= 'z'; c++){chs[i] = c;String next = new String(chs);if(!dict.contains(next)) continue;if(endSet.contains(next)) return step + 1;nextSet.add(next);}chs[i] = old;}}return nextSet.size() > endSet.size() ? bfs(endSet, nextSet, dict, step) : bfs(nextSet, endSet, dict, step);}
}

LeetCode - 126. Word LadderII

题目链接

题目

解析

单向BFS解法:

• 记录当前扩展的next的parent是cur即可；
• 但是这里每个next可能有多个parent，所以在循环中，不能先移除dict.remve(next)，而是使用一个set集合used数组先标记，退出这次循环之后再一次性移除；
• 最后从endWord往前DFS求出路径即可(中间集合使用LinkedList(可以支持头部插入))；

使用单向BFS + DFS:

class Solution {public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {List<List<String>> res = new ArrayList<>();if (wordList == null || wordList.isEmpty())return res;Set<String> dict = new HashSet<>(wordList);if (!dict.contains(endWord))return res;dict.remove(beginWord);Set<String> used = new HashSet<>();  //不能像前一题一样，找到一个就移除一个，而是搞完一层，才一次性移除Map<String, HashSet<String>> parents = new HashMap<>(); //当前节点(单词)的所有的父亲Queue<String> queue = new LinkedList<>();queue.add(beginWord);boolean found = false;while (!queue.isEmpty() && !found) {int qsize = queue.size();for (int size = 0; size < qsize; size++) {String cur = queue.poll();for (int i = 0; i < cur.length(); i++) {char[] chs = cur.toCharArray();for (char c = 'a'; c <= 'z'; c++) {if (c == chs[i])continue;chs[i] = c;String next = new String(chs);if (!dict.contains(next))continue;if (next.equals(endWord))  // 就算找到了，还是要做完当前这一层found = true;queue.add(next);parents.computeIfAbsent(next, k -> new HashSet<>()).add(cur);// next的其中一个父亲为curused.add(next);// 只是记录，而不是直接dict.remove(next)}}}dict.removeAll(used);  // 不能像前一题单向那样直接在循环里面移除 next, 而是在这里(这一层结束之后)，才移除，不然会丢失路径 例如 : dog->cog, log->cogused.clear();}if (!found)return res;//DFS从节点的parent集合中求解答案LinkedList<String> list = new LinkedList<>(); // 中间变量list.add(endWord);dfs(parents, res, endWord, beginWord, list); //backtrack from the endWord(child) to beginWord(parent)return res;}private void dfs(Map<String, HashSet<String>> parents, List<List<String>> res,String curStr, String beginWord, LinkedList<String> list) {if (curStr.equals(beginWord)) { //到了起点， 找到一条了res.add(new ArrayList<>(list));return;}for (String parent : parents.get(curStr)) {list.addFirst(parent);   // 注意是加到开头dfs(parents, res, parent, beginWord, list);list.removeFirst();      // backtrack}}
}

另外可以添加一个Map steps记录每一个节点的最短路径长度(层数) (这题不需要):

测试:

import java.util.*;public class Solution {public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {List<List<String>> res = new ArrayList<>();if (wordList == null || wordList.isEmpty())return res;Set<String> dict = new HashSet<>(wordList);if (!dict.contains(endWord))return res;dict.remove(beginWord);Set<String> used = new HashSet<>();  //不能像前一题一样，找到一个就移除一个，而是搞完一层，才一次性移除Map<String, HashSet<String>> parents = new HashMap<>(); //当前单词的所有的父亲Map<String, Integer> steps = new HashMap<>(); // 扩展到当前单词所需要的最小步数Queue<String> queue = new LinkedList<>();queue.add(beginWord);boolean found = false;int step = 0;while (!queue.isEmpty() && !found) {int qsize = queue.size();++step;for (int size = 0; size < qsize; size++) {String cur = queue.poll();for (int i = 0; i < cur.length(); i++) {char[] chs = cur.toCharArray();for (char c = 'a'; c <= 'z'; c++) {if (c == chs[i])continue;chs[i] = c;String next = new String(chs);if (!dict.contains(next))continue;if (next.equals(endWord))  // 就算找到了，还是要做完当前这一层found = true;queue.add(next);steps.put(next, step + 1);parents.computeIfAbsent(next, k -> new HashSet<>()).add(cur);used.add(next);}}}dict.removeAll(used);  // 不能像前一题那样直接在循环里面移除 next, 而是在这里(这一层结束之后)，才移除，不然会丢失路径 例如 : dog->cog, log->cogused.clear();}if (!found)return res;LinkedList<String> list = new LinkedList<>(); // 中间变量list.add(endWord);dfs(parents, res, endWord, beginWord, list); //backtrack from the endWord(child) to beginWord(parent)System.out.println(steps); //输出 stepsreturn res;}private void dfs(Map<String, HashSet<String>> parents, List<List<String>> res,String curStr, String beginWord, LinkedList<String> list) {if (curStr.equals(beginWord)) { //到了起点， 找到一条了res.add(new ArrayList<>(list));return;}for (String parent : parents.get(curStr)) {list.addFirst(parent);   // 注意是加到开头dfs(parents, res, parent, beginWord, list);list.removeFirst();      // backtrack}}public static void main(String[] args) {String beginWord = "hit";String endWord = "cog";List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");System.out.println(new Solution().findLadders(beginWord, endWord, wordList));}
}

输出:

{lot=3, log=4, dot=3, cog=5, hot=2, dog=4}
[[hit, hot, lot, log, cog], [hit, hot, dot, dog, cog]]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！