leetcode 126. Word Ladder II (双向BFS + DFS）

2024-01-31 00:56| 来源: 网络整理| 查看: 265

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. Note:

Return an empty list if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. Example 1:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

Output: [ [“hit”,“hot”,“dot”,“dog”,“cog”], [“hit”,“hot”,“lot”,“log”,“cog”] ] Example 2:

Input: beginWord = “hit” endWord = “cog” wordList = [“hot”,“dot”,“dog”,“lot”,“log”]

Output: []

Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

127题的升级版，127题只要求输出最短路径是多长，而本题让输出所有的最短路径

思路：还是127题的双向BFS思路，但是因为要输出所有的路径，中间不能在wordList中把单词删除，因为可能多个路径用到同一个单词

而且一个单词可以改变不同的位变成多个单词，因此需要一个parent和children的关系，利用这个parent和children的关系，用DFS即可找到所有的路径

同时注意因为是双向的，如果方向是反向的，parent会变成child，而child是parent

思路是参照某大神的方法因为很复杂，具体思路写在代码注释里面

//18ms, faster than 94.15% (current time).. public List findLadders(String beginWord, String endWord, List wordList) { HashSet dict = new HashSet(wordList); List result = new ArrayList(); //each transformed word must exist in word list, beginWord is not a transformed word.. if (!dict.contains(endWord)) { return result; } boolean found = false; boolean backward = false; //true when from q2 to q1.. int len = beginWord.length(); //save parent word and their children.. HashMap children = new HashMap(); //bidirection BFS, begin and end queue.. HashSet q1 = new HashSet() {{add(beginWord);}}; HashSet q2 = new HashSet() {{add(endWord);}}; while (!q1.isEmpty() && !q2.isEmpty() && !found) { if (q1.size() > q2.size()) { //swap q1 and q2.. HashSet tmp = q2; q2 = q1; q1 = tmp; //if swap, then direction be opposite.. backward = !backward; } //remove word in q1, q2 from dict to prevent duplicated words.. for (String word : q1) { dict.remove(word); } for (String word : q2) { dict.remove(word); } HashSet queue = new HashSet(); //BFS next level.. //this for part is a level in BFS.. for (String word : q1) { //cannot change String word, change to char array.. char[] cWord = word.toCharArray(); for (int i = 0; i cWord[i] = c; //cannot put this parent outside for loop.. //because when backward, parent has changed.. String parent = word; String child = String.valueOf(cWord); //char array to String.. if (q2.contains(child)) { //found the destination.. found = true; //add parent child pair.. //but if backward is true, parent and child are opposite.. if (backward) { String tmp = parent; parent = child; child = tmp; } if (children.get(parent) == null) { List tmpChildren = new ArrayList(); tmpChildren.add(child); children.put(parent, tmpChildren); } else { children.get(parent).add(child); } //if already found, means founded in previous level(shorter path).. //so this path is not necessary.. } else if (dict.contains(child) && !found) { //add this child word to queue for next level BFS.. queue.add(child); //add parent, child pair to children.. //but if backward is true, they are opposite.. if (backward) { String tmp = parent; parent = child; child = tmp; } if (children.get(parent) == null) { List tmpChildren = new ArrayList(); tmpChildren.add(child); children.put(parent, tmpChildren); } else { children.get(parent).add(child); } } } //after try every bit, revert it.. cWord[i] = before; } } q1 = queue; } if (found) { List path = new ArrayList() {{add(beginWord);}}; //every path in result.. getPath(beginWord, endWord, path, children, result); } return result; } //use DFS to find all the path from parent, child pair.. public void getPath(String beginWord, String endWord, List path, HashMap children, List result) { if (beginWord.equals(endWord)) { //create new list of path, cannot add path reference directly.. List tmpPath = new ArrayList(path); result.add(tmpPath); return; } //some path stopped because is not the shortest, so have no child.. if (!children.containsKey(beginWord)) { return; } //DFS.. for (String word : children.get(beginWord)) { path.add(word); getPath(word, endWord, path, children, result); path.remove(word); } }

【本文地址】

公司简介

联系我们