[关闭]
@Yano 2019-09-20T10:49:08.000000Z 字数 4249 阅读 1717

LeetCode Breadth First Search 题目汇总

LeetCode


公众号

coding 笔记、点滴记录,以后的文章也会同步到公众号(Coding Insight)中,希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

127 Word Ladder

https://leetcode.com/problems/word-ladder/description/

题目描述

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

代码

  1. class Solution {
  2. public int ladderLength(String beginWord, String endWord, List<String> wordList) {
  3. Set<String> set = new HashSet<>(wordList);
  4. LinkedList<String> queue = new LinkedList<>();
  5. // 在队列中放入初始元素
  6. queue.offer(beginWord);
  7. int step = 2;
  8. while (!queue.isEmpty()) {
  9. // 下一步具有的节点数
  10. int size = queue.size();
  11. while (size > 0) {
  12. String currString = queue.poll();
  13. Iterator<String> iterator = set.iterator();
  14. while (iterator.hasNext()) {
  15. String next = iterator.next();
  16. int diff = diff(next, currString);
  17. // 若当前元素与取出元素差1,并且是endWord,则直接返回结果
  18. if (diff == 1 && next.equals(endWord)) {
  19. return step;
  20. }
  21. // 差1就放入队列,并将其删除(此元素可以删除,因为循环读取时长度不是最优解)
  22. if (diff == 1) {
  23. queue.offer(next);
  24. iterator.remove();
  25. }
  26. }
  27. size--;
  28. }
  29. step++;
  30. }
  31. return 0;
  32. }
  33. private int diff(String s1, String s2) {
  34. if (s1.length() != s2.length()) {
  35. return 0;
  36. }
  37. int diff = 0;
  38. for (int i = 0; i < s1.length(); i++) {
  39. if (s1.charAt(i) != s2.charAt(i)) {
  40. diff++;
  41. }
  42. if (diff >= 2) {
  43. return 2;
  44. }
  45. }
  46. return diff;
  47. }
  48. }

126 Word Ladder II

https://leetcode.com/problems/word-ladder-ii/description/

题目描述

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

分析

部分可以依照上一题,但是这道题是求「所有的最短路径」,而不是「最短路径长度」,单纯的 BFS 无法实现。但是可以使用 BFS 构造数据结构(保证最短路径),并使用 DFS 求路径。

Version 1:没有构造通用的数据结构,map 的 value 记录步骤,在 DFS 时也要重新计算两个字符串差异数。用 set 表示是否 visit 过。

代码

  1. class Solution {
  2. public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
  3. // value:从begin到达该key的最短长度。
  4. Map<String, Integer> map = new HashMap<>();
  5. Set<String> notVisitSet = new HashSet<>(wordList);
  6. List<List<String>> ans = new ArrayList<>();
  7. if (!notVisitSet.contains(endWord)) {
  8. return ans;
  9. }
  10. // 构建map
  11. bfs(beginWord, endWord, map, notVisitSet);
  12. if (map.isEmpty()) {
  13. return ans;
  14. }
  15. map.put(beginWord, 0);
  16. // 从end指向begin,否则会超时!因为begin后面可能接多个路径,但是end只有一个
  17. dfs(endWord, beginWord, map, ans, new ArrayList<>(Arrays.asList(endWord)));
  18. return ans;
  19. }
  20. private void bfs(String beginWord, String endWord, Map<String, Integer> map, Set<String> notVisitSet) {
  21. LinkedList<String> queue = new LinkedList<>();
  22. // 在队列中放入初始元素
  23. queue.offer(beginWord);
  24. boolean find = false;
  25. int level = 1;
  26. while (!queue.isEmpty()) {
  27. int size = queue.size();
  28. while (size > 0) {
  29. String curr = queue.poll();
  30. Iterator<String> iterator = notVisitSet.iterator();
  31. while (iterator.hasNext()) {
  32. String next = iterator.next();
  33. int diff = diff(curr, next);
  34. if (diff == 1) {
  35. // 若在某一步找到,则当前步数结束即可
  36. if (next.equals(endWord)) {
  37. find = true;
  38. }
  39. queue.offer(next);
  40. iterator.remove();
  41. map.put(next, level);
  42. }
  43. }
  44. size--;
  45. }
  46. if (find) {
  47. break;
  48. }
  49. level++;
  50. }
  51. }
  52. private void dfs(String beginWord, String endWord, Map<String, Integer> map, List<List<String>> ans,
  53. List<String> tmp) {
  54. if (beginWord.equals(endWord)) {
  55. List<String> arrayList = new ArrayList<>(tmp);
  56. Collections.reverse(arrayList);
  57. ans.add(arrayList);
  58. return;
  59. }
  60. for (String key : map.keySet()) {
  61. // 要判断 diff,因为本层和下一层没有必然联系
  62. if (map.get(key) == map.get(beginWord) - 1 && diff(beginWord, key) == 1) {
  63. tmp.add(key);
  64. dfs(key, endWord, map, ans, tmp);
  65. tmp.remove(tmp.size() - 1);
  66. }
  67. }
  68. }
  69. private int diff(String s1, String s2) {
  70. if (s1.length() != s2.length()) {
  71. return 0;
  72. }
  73. int diff = 0;
  74. for (int i = 0; i < s1.length(); i++) {
  75. if (s1.charAt(i) != s2.charAt(i)) {
  76. diff++;
  77. }
  78. if (diff >= 2) {
  79. return 2;
  80. }
  81. }
  82. return diff;
  83. }
  84. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注