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);
}
在这里，只有当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