我女儿刚才看书看哭了。# Parenting - 为人父母
z*e
1 楼
这题也够坑爹的
public class Solution {
public ArrayList> findLadders(String start, String end
, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
dict.add(start);
dict.add(end);
HashMap> routs = new HashMap>();
this.generateRouts(dict, routs);
ArrayList> result = new ArrayList
LinkedList queue = new LinkedList();
queue.add(new Node(null, 0, start));
int previousLevel = 0;
Map visited = new HashMap();
while(!queue.isEmpty()){
Node node = queue.pollFirst();
if(node.val.equals(end)){
if(previousLevel == 0 || node.level == previousLevel){
this.generateResults(node, result);
}else{
break;
}
}else{
Set values = routs.get(node.val);
if(values == null || values.size() == 0) continue;
Set removeSet = new HashSet();
for(String value:values){
if(visited.containsKey(value)&&node.level+1>visited.get(
value)){
removeSet.add(value);
}else{
queue.add(new Node(node, node.level+1,value));
visited.put(value,node.level+1);
if(routs.containsKey(value)) routs.get(value).remove
(node.val);
}
}
values.removeAll(removeSet);
}
}
return result;
}
private void generateResults(Node node, ArrayList>
result){
ArrayList list = new ArrayList();
while(node!=null){
list.add(0,node.val);
node = node.parent;
}
result.add(list);
}
public void generateRouts(HashSet set, HashMap
for(String string:set){
char[] c = string.toCharArray();
for(int i=0;i
for(char t = 'a';t<='z';t++){
if(t==old) continue;
c[i] = t;
String temp = new String(c);
if(set.contains(temp)){
HashSet s = routs.get(string);
if(s == null){
s = new HashSet();
routs.put(string, s);
}
s.add(temp);
}
}
c[i] = old;
}
}
}
}
class Node{
Node parent;
int level;
String val;
public Node(Node parent, int level, String val){
this.parent = parent;
this.level = level;
this.val = val;
}
}
public class Solution {
public ArrayList
, HashSet
// Start typing your Java solution below
// DO NOT write main() function
dict.add(start);
dict.add(end);
HashMap
this.generateRouts(dict, routs);
ArrayList
LinkedList
queue.add(new Node(null, 0, start));
int previousLevel = 0;
Map
while(!queue.isEmpty()){
Node node = queue.pollFirst();
if(node.val.equals(end)){
if(previousLevel == 0 || node.level == previousLevel){
this.generateResults(node, result);
}else{
break;
}
}else{
Set
if(values == null || values.size() == 0) continue;
Set
for(String value:values){
if(visited.containsKey(value)&&node.level+1>visited.get(
value)){
removeSet.add(value);
}else{
queue.add(new Node(node, node.level+1,value));
visited.put(value,node.level+1);
if(routs.containsKey(value)) routs.get(value).remove
(node.val);
}
}
values.removeAll(removeSet);
}
}
return result;
}
private void generateResults(Node node, ArrayList
result){
ArrayList
while(node!=null){
list.add(0,node.val);
node = node.parent;
}
result.add(list);
}
public void generateRouts(HashSet
for(String string:set){
char[] c = string.toCharArray();
for(int i=0;i
for(char t = 'a';t<='z';t++){
if(t==old) continue;
c[i] = t;
String temp = new String(c);
if(set.contains(temp)){
HashSet
if(s == null){
s = new HashSet
routs.put(string, s);
}
s.add(temp);
}
}
c[i] = old;
}
}
}
}
class Node{
Node parent;
int level;
String val;
public Node(Node parent, int level, String val){
this.parent = parent;
this.level = level;
this.val = val;
}
}
