DOL Session Reveals Vital Information Regarding PERM Reforms# EB23 - 劳工卡
l*d
1 楼
尝试过许多解法，但老是 TLE. 有高人能帮忙看一下这一段代码吗？
基本上就是 double queue + backtracking，跟这里的http://blog.csdn.net/niaokedaoren/article/details/8884938
很相似。但是问题出在哪里呢？
提前谢谢了！
------------------------------------------------------------------------
import java.util.Map;
public class Solution {
public void fillPaths(String start, String cur, Map>
map,
ArrayList> result, LinkedList post
) {
post.addFirst(cur);
if (start.equals(cur)) {
result.add(new ArrayList(post));
} else {
for (String prev : map.get(cur)) {
fillPaths(start,prev,map,result,post);
}
}
post.removeFirst();
}
public ArrayList> findLadders(String start, String end
, HashSet dict) {
dict.add(start);
dict.add(end);
Map> visited = new HashMap>();
ArrayList> result = new ArrayList
Queue next, current;
current = new LinkedList();
next = new LinkedList();
next.offer(start);
visited.put(start, new HashSet());
while (true) {
Queue temp = current;
current = next;
next = temp;
next.clear();
for (String n : current) dict.remove(n);
for (String s : current) {
for (int i = 0; i < s.length(); i++) {
StringBuilder sb = new StringBuilder(s);
for (char c = 'a'; c <= 'z'; c++) {
if (c == s.charAt(i)) continue;
sb.setCharAt(i, c);
String s1 = sb.toString();
if (dict.contains(s1)) {
next.add(s1);
Set set;
if (visited.containsKey(s1)) set = visited.get(
s1);
else set = new HashSet();
set.add(s);
visited.put(s1,set);
}
}
}
}
if (next.isEmpty()) return result;
if (next.contains(end)) break;
}
fillPaths(start,end,visited,result,new LinkedList());
return result;
}
------------------------------------------------------------------------
基本上就是 double queue + backtracking，跟这里的http://blog.csdn.net/niaokedaoren/article/details/8884938
很相似。但是问题出在哪里呢？
提前谢谢了！
------------------------------------------------------------------------
import java.util.Map;
public class Solution {
public void fillPaths(String start, String cur, Map
map,
ArrayList
) {
post.addFirst(cur);
if (start.equals(cur)) {
result.add(new ArrayList
} else {
for (String prev : map.get(cur)) {
fillPaths(start,prev,map,result,post);
}
}
post.removeFirst();
}
public ArrayList
, HashSet
dict.add(start);
dict.add(end);
Map
ArrayList
Queue
current = new LinkedList
next = new LinkedList
next.offer(start);
visited.put(start, new HashSet
while (true) {
Queue
current = next;
next = temp;
next.clear();
for (String n : current) dict.remove(n);
for (String s : current) {
for (int i = 0; i < s.length(); i++) {
StringBuilder sb = new StringBuilder(s);
for (char c = 'a'; c <= 'z'; c++) {
if (c == s.charAt(i)) continue;
sb.setCharAt(i, c);
String s1 = sb.toString();
if (dict.contains(s1)) {
next.add(s1);
Set
if (visited.containsKey(s1)) set = visited.get(
s1);
else set = new HashSet
set.add(s);
visited.put(s1,set);
}
}
}
}
if (next.isEmpty()) return result;
if (next.contains(end)) break;
}
fillPaths(start,end,visited,result,new LinkedList
return result;
}
------------------------------------------------------------------------