Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
Given:
start =
"hit"
end =
"cog"
dict =
["hot","dot","dog","lot","log"]
Return
[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
先从end 到start build a tree.
再从start 到end,做dfs查找所有的边即可。
思路很简单。方法和1 一样,就是在寻找边的时候,再用一个queuePath来记录,当前节点,所用的节点
下面的这个实现,超时了。
public class Solution { public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) { ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>(); // First add the start and end string if they are not presented. LinkedList<String> queue = new LinkedList<String>(); LinkedList<Integer> qLevel = new LinkedList<Integer>(); LinkedList<ArrayList<String>> queueList = new LinkedList<ArrayList<String>>(); dict.add(end); queue.add(start); qLevel.add(1); int minLevel2end = Integer.MAX_VALUE; ArrayList<String> al = new ArrayList<String>(); al.add(start); queueList.add(al); while (!queue.isEmpty()) { String str = queue.poll();// current searching node int curLevel = qLevel.poll(); if (curLevel >= minLevel2end) { break; } ArrayList<String> curPath = queueList.poll(); // we can remove the just visited node to speed up dict.remove(str); // instead of searching through dict to find its match, // we manually find its permuation and find in dict char[] chars = str.toCharArray(); for (int i = 0; i < start.length(); i++) { char oldCh = chars[i]; for (char ch = 'a'; ch <= 'z'; ch++) { if (ch == oldCh) continue; chars[i] = ch; String newStr = new String(chars); // chars.toString() is // wrong if (dict.contains(newStr)) { ArrayList<String> newPath = new ArrayList<String>(curPath); newPath.add(newStr); if (newStr.equals(end)) { // do not add into dict minLevel2end = Math.min(minLevel2end, curLevel + 1); if (curLevel + 1 == minLevel2end)// having find the // end all.add(newPath); } else { queue.add(newStr);// BFS qLevel.add(curLevel + 1); queueList.add(newPath);// record path } } } chars[i] = oldCh; } } return all; } }查看代码,当数据很大的时候,
ArrayList<String> newPath = copyList(curPath); 可能copy了很多无效的,最后不能达到最终节点的path。
therefore, instead of copying every possible path, we use a tree to remember it.
And at the end, we traval from 'end' to 'start' to find all possible path.
这里,我们就给每个节点,建立了一个p 指针(以前是用的链表,现在我们用HashSet来表示parent链表。
public class WordLadderII2 { public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) { dict.add(end); LinkedList<String> queue = new LinkedList<String>(); HashMap<String, Node> work2NodeMap = new HashMap<String, Node>(); queue.add(start); Node tmp = new Node(start, 1); work2NodeMap.put(start, tmp); // store the Strings that are can be used as the next while (!queue.isEmpty()) { String curStr = queue.poll(); dict.remove(curStr); Node curNode = work2NodeMap.get(curStr); if (curStr.equals(end)) { // just found the end break; } // list all one step permuation char[] chars = curStr.toCharArray(); for (int i = 0; i < chars.length; i++) { char oldChar = chars[i]; for (char j = 'a'; j <= 'z'; j++) { if (j == oldChar) continue; chars[i] = j; String childStr = new String(chars);// chars.toSting() is // WRONG // compare newStr and curStr, and modify the parant // relantionship if (!dict.contains(childStr)) { continue; } Node childNode = work2NodeMap.get(childStr); if (childNode == null) { // not exist childNode = new Node(childStr, curNode.depth + 1); work2NodeMap.put(childStr, childNode); } // if childNode already been discovered if ((childNode.depth >= curNode.depth+1 )) { childNode.depth = curNode.depth+1; childNode.p.add(curNode); queue.add(childStr); } } chars[i] = oldChar; } dict.remove(curStr); } return listAllPath(end, work2NodeMap); } private ArrayList<ArrayList<String>> listAllPath(String end, HashMap<String, Node> work2NodeMap) { // build all the pathes from the work2NodeMap ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>(); Node endNode = work2NodeMap.get(end); if (endNode != null) { ArrayList<String> curList = new ArrayList<String>(); DFS(endNode, curList, all); } return all; } private void DFS(Node curNode, ArrayList<String> curList, ArrayList<ArrayList<String>> all) { // DFS list all pathes curList.add(0, curNode.str); if (curNode.depth == 1) { all.add(curList); } else { for (Node parent : curNode.p) if(parent.depth == curNode.depth - 1){ ArrayList<String> newList = new ArrayList<String>(curList); DFS(parent, newList , all); } } } } class Node { String str; int depth; HashSet<Node> p; Node(String s, int d) { str = s; depth = d; p = new HashSet<Node>(); } }
---------------------------------------------------------------------
哎,折腾完了,发现网上自己的思路,基本都被人想过,研究过了。哎,泯然众人矣
Mistakes:
1: 打印的结果,变成逆序的了。应该是insert到最前面
2:即使是第二遍的时候,也还是不能用 DFS,会搞得太深,超过BFS的限制。
3: 第二遍,找path的时候,不能remove刚刚找到的点的。
4: 在每一级搜索的时候,为避免重复寻找该位置的相似的。我们要先删去,找完再加回去。
5: 重大失误, 哎, 脑子晕了, 应该是新的string和end对比。
if (newStr.equals(end)) { // do not add into dict
可是,我开始写成了
if (str.equals(end)) { // do not add into dict
脑子不清醒的时候,真心不能coding
6:第一遍coding的时候,记住了,不能在dict里先加入end,可是,第二遍的时候,就直接加入了。脑子晕,Tiger
7:注意:end和start都不在dict里 , 所以,我们要先把end 加到dict里
8: 在建立map的时候,要只把有用 的拿到。而不能全部加进来。
9: DFS 的时候,也要check 节点的 distance
10 : DFS 的时候,曾经出现过重复的路径,导致了无限循环, 原因就在于 bins 节点的parentlist里,出现了两次bands节点。(到底还是没搞清楚为什么parent 会加入多次。 嗯,发现,也就是在level ==3 的节点上,其parent节点 (level == 2, start的level ==1)可能 为2个。
解决方法是,把p的类型设为HashSet. 当然,也可以继续用ArrayList, 但那样,加入的时候,要看是否已经存在。
--------------------------------第二遍做的时候,的错误------------------------------------------
1: queue的时候, 因为是用LinkedList实现Queue, 错用了push()操作(这是对stack的), 应该用add. ---------------哎,就这一个问题,搞了半小时。 不爽~~~~~~~~~~~
不过,确实,第二次做,就有思路了,直接coding完毕, 就犯了上面这一个错误。
2:建立完parent关系后,再从end节点BFS,要找到start节点后,再copyList。 否则,很耗时间。
3: 哎, 又一次犯了这个错误: 新建的Node类里,要把parent的类型设为HashSet类型。
class Node {
String str;
int depth;
HashSet<Node> p;
Node(String s, int d) {
str = s;
depth = d;
p = new HashSet<Node>();
}
}
4: 哎,代码对比,我的第二个解法,比网上找到的解法,在strs.length == 4565 这种large input 时, 要多用了一倍的时间。 ???? 哎
经分析, findPath只用了不到1%的时间。 大部分时间都是被while loope给用掉了。
哈哈,终于找到原因了。 就是在 这里
Node childNode = work2NodeMap.get(childStr);
if (childNode == null) { // not exist
childNode = new Node(childStr, curNode.depth + 1);
work2NodeMap.put(childStr, childNode);
}
// if childNode already been discovered
if ((childNode.depth >= curNode.depth+1 )) {
childNode.depth = curNode.depth+1;
childNode.p.add(curNode);
queue.add(childStr);
}
这里,其实,只有childNode第一次被发现的时候,才需要加入到queue里,而不是像上述代码一样。 为了少几层括号,就分散开来。 在更动parent关系之后, 不管不顾地将其加入到queue里。------ 最新的代码如上。在这里,只有当child == null 的时候,我们才需要将新发现的(第一次发现)的Node加入到queue里。 嗯,当时是头脑不清晰,想反正加了不会错,就加了。
那,这样来讲,Node.p 的关系,是清晰的,上面问题3 就不是问题了,完全可以 用回原来的ArrayList来表示parents 链表
Learned:
1:eclipse crash。 可以把工作目录下的
2: HashSet的优势在于 检索的性能。简单的说它的Contains方法的性能在大数据量时比List<T>好得多。HashSet<T>的Contains方法复杂度是O(1),List<T>的Contains方法复杂度是O(n)。
因此,我们不应该自己替换成对象的List检索。
3:在leetcode中, Hashtable不支持,但是HashMap 类,还是可以的。-----------哎,要TMD早知道,能省一晚上的力气, TNND~~~~~~~~~~~~~~~
4:ArrayList 在new 一个对象的时候, 可以直接用另一个ArrayList作为参数,那样,直接就copy了。 --------> 就不用自己写 copyList()这个函数。
5: Queue 作为一个接口, 可以这样实现
Queue<String> queue = new LinkedList<String>();
*******************下面是accept的代码,来自网上, 找时间看吧。(跟自己的思路2 的代码,完全完全一样。 上面的)***********
No comments:
Post a Comment