b****z 发帖数: 176 | 1 代码如下:
基本思路是,用queue 进行BFS,记录了每个node的parent,找到之后,通过parent来
recover path。感觉没有任何冗余计算啊!!!为什么过不了?
谢谢各位!!
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
Queue queue = new LinkedList();
queue.add(new Wrapper(start, null));
queue.add(null);
boolean flag = false;
boolean find = false;
visited.add(start);
Set curLayer = new HashSet();
while (!queue.isEmpty()) {
Wrapper cur = queue.poll();
if (cur == null) {
if (flag || find) break;
queue.add(null);
flag = true;
visited.addAll(curLayer);
curLayer.clear();
continue;
}
flag = false;
List list = getAllNeighbours(cur.cur, dict, visited);
for (String itr : list) {
if (visited.contains(itr)) continue;
if (itr.equals(end)) find = true;
queue.add(new Wrapper(itr, cur));
curLayer.add(itr);
}
visited.addAll(curLayer);
}
if (find) {
for (Wrapper wrapper : queue) {
if (wrapper.cur.equals(end)) {
List temp = formPath(wrapper);
res.add(temp);
}
}
}
return res;
}
public static List getAllNeighbours(String s, Set dict,
Set visited) {
List res = new ArrayList();
for (int i = 0; i < s.length(); i++) {
for (char j = 'a'; j <= 'z'; j++) {
if (j == s.charAt(i)) continue;
StringBuilder builder = new StringBuilder(s);
builder.setCharAt(i, j);
String temp = builder.toString();
if (dict.contains(builder.toString())) {
if (visited.contains(temp)) continue;
res.add(temp);
}
}
}
return res;
}
public List formPath(Wrapper wrapper) {
List res = new ArrayList();
Wrapper cur = wrapper;
while (cur != null) {
res.add(cur.cur);
cur = cur.parent;
}
Collections.reverse(res);
return res;
}
public class Wrapper {
String cur;
Wrapper parent;
Wrapper(String cur, Wrapper parent) {
this.cur = cur;
this.parent = parent;
}
}
} | a******l 发帖数: 72 | 2 TLE?我的也是,不同的版本,一个几周前过了,一个昨天的就没有。你可一先local
debug 一下。。。 | P*******L 发帖数: 2637 | 3 这个题用 Java 写很难过,但同样的算法 C++ 过很容易。
【在 b****z 的大作中提到】 : 代码如下: : 基本思路是,用queue 进行BFS,记录了每个node的parent,找到之后,通过parent来 : recover path。感觉没有任何冗余计算啊!!!为什么过不了? : 谢谢各位!! : import java.util.ArrayList; : import java.util.HashSet; : import java.util.LinkedList; : import java.util.List; : import java.util.Queue; : import java.util.Set;
| b****z 发帖数: 176 | 4
本地都是对的。但是不知道为什么过不了大数据
【在 a******l 的大作中提到】 : TLE?我的也是,不同的版本,一个几周前过了,一个昨天的就没有。你可一先local : debug 一下。。。
| b****z 发帖数: 176 | 5
但是也看到有人 java过得,所以想问问是不是自己算法有问题
【在 P*******L 的大作中提到】 : 这个题用 Java 写很难过,但同样的算法 C++ 过很容易。
| A****L 发帖数: 138 | 6 这个事我以前开的帖子。
http://www.mitbbs.com/article_t0/JobHunting/32682961.html
代码如下:
public class Solution {
public class Ladder {//Define Ladder class it's important
public ArrayList parentList;
public String word;
public Ladder(String w, Ladder parent) {word=w; parentList = new
ArrayList(); parentList.add(parent);}
}
ArrayList> ladders=new ArrayList>();;
public ArrayList> findLadders(String start, String end
, HashSet dict) {
Ladder endLadder = new Ladder(end,null), startLadder=null;
Queue q = new ArrayDeque();
q.add(endLadder);//Here we look from end to start because we need to
reverse the output
int count=1,len = start.length(); //count the number of words for
each level
while(!q.isEmpty() && startLadder==null) {
HashMap map = new HashMap();
int cur=0;
for(int i=0;i
Ladder curLadder = q.poll();
for(int j=0;j
of 26 letters
char[] wordChar = curLadder.word.toCharArray();
for(char c='a';c<='z';c++) {
wordChar[j]=c;
String s = new String(wordChar);
if(s.equals(start)) {//found
if(startLadder!=null) startLadder.parentList.add
(curLadder); // if this is not the first time found
else startLadder = new Ladder(start, curLadder);
}
else if(dict.contains(s) && !s.equals(curLadder.word
)) {//filter those not in dict
Ladder newLadder = new Ladder(s,curLadder);
q.add(newLadder);
map.put(s,newLadder);
cur++;// increase the number of nodes of the
next level
dict.remove(s);
}
else if(map.containsKey(s)) map.get(s).parentList.
add(curLadder); //Same level then reuse the revious existing
}
}
}
count=cur;
}
if(startLadder!=null) buildLadders(new ArrayList(),
endLadder, startLadder);
return ladders;
}
public void buildLadders(ArrayList list,Ladder end, Ladder cur) {
list.add(cur.word);
if(cur==end) ladders.add(new ArrayList(list));
else for(Ladder l:cur.parentList) buildLadders(list,end,l);
list.remove(list.size()-1);
}
}
【在 b****z 的大作中提到】 : 代码如下: : 基本思路是,用queue 进行BFS,记录了每个node的parent,找到之后,通过parent来 : recover path。感觉没有任何冗余计算啊!!!为什么过不了? : 谢谢各位!! : import java.util.ArrayList; : import java.util.HashSet; : import java.util.LinkedList; : import java.util.List; : import java.util.Queue; : import java.util.Set;
| b****z 发帖数: 176 | 7 代码如下:
基本思路是,用queue 进行BFS,记录了每个node的parent,找到之后,通过parent来
recover path。感觉没有任何冗余计算啊!!!为什么过不了?
谢谢各位!!
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> res = new ArrayList>();
Set visited = new HashSet();
Queue queue = new LinkedList();
queue.add(new Wrapper(start, null));
queue.add(null);
boolean flag = false;
boolean find = false;
visited.add(start);
Set curLayer = new HashSet();
while (!queue.isEmpty()) {
Wrapper cur = queue.poll();
if (cur == null) {
if (flag || find) break;
queue.add(null);
flag = true;
visited.addAll(curLayer);
curLayer.clear();
continue;
}
flag = false;
List list = getAllNeighbours(cur.cur, dict, visited);
for (String itr : list) {
if (visited.contains(itr)) continue;
if (itr.equals(end)) find = true;
queue.add(new Wrapper(itr, cur));
curLayer.add(itr);
}
visited.addAll(curLayer);
}
if (find) {
for (Wrapper wrapper : queue) {
if (wrapper.cur.equals(end)) {
List temp = formPath(wrapper);
res.add(temp);
}
}
}
return res;
}
public static List getAllNeighbours(String s, Set dict,
Set visited) {
List res = new ArrayList();
for (int i = 0; i < s.length(); i++) {
for (char j = 'a'; j <= 'z'; j++) {
if (j == s.charAt(i)) continue;
StringBuilder builder = new StringBuilder(s);
builder.setCharAt(i, j);
String temp = builder.toString();
if (dict.contains(builder.toString())) {
if (visited.contains(temp)) continue;
res.add(temp);
}
}
}
return res;
}
public List formPath(Wrapper wrapper) {
List res = new ArrayList();
Wrapper cur = wrapper;
while (cur != null) {
res.add(cur.cur);
cur = cur.parent;
}
Collections.reverse(res);
return res;
}
public class Wrapper {
String cur;
Wrapper parent;
Wrapper(String cur, Wrapper parent) {
this.cur = cur;
this.parent = parent;
}
}
} | a******l 发帖数: 72 | 8 TLE?我的也是,不同的版本,一个几周前过了,一个昨天的就没有。你可一先local
debug 一下。。。 | P*******L 发帖数: 2637 | 9 这个题用 Java 写很难过,但同样的算法 C++ 过很容易。
【在 b****z 的大作中提到】 : 代码如下: : 基本思路是,用queue 进行BFS,记录了每个node的parent,找到之后,通过parent来 : recover path。感觉没有任何冗余计算啊!!!为什么过不了? : 谢谢各位!! : import java.util.ArrayList; : import java.util.HashSet; : import java.util.LinkedList; : import java.util.List; : import java.util.Queue; : import java.util.Set;
| b****z 发帖数: 176 | 10
本地都是对的。但是不知道为什么过不了大数据
【在 a******l 的大作中提到】 : TLE?我的也是,不同的版本,一个几周前过了,一个昨天的就没有。你可一先local : debug 一下。。。
| | | b****z 发帖数: 176 | 11
但是也看到有人 java过得,所以想问问是不是自己算法有问题
【在 P*******L 的大作中提到】 : 这个题用 Java 写很难过,但同样的算法 C++ 过很容易。
| A****L 发帖数: 138 | 12 这个事我以前开的帖子。
http://www.mitbbs.com/article_t0/JobHunting/32682961.html
代码如下:
public class Solution {
public class Ladder {//Define Ladder class it's important
public ArrayList parentList;
public String word;
public Ladder(String w, Ladder parent) {word=w; parentList = new
ArrayList(); parentList.add(parent);}
}
ArrayList> ladders=new ArrayList>();;
public ArrayList> findLadders(String start, String end
, HashSet dict) {
Ladder endLadder = new Ladder(end,null), startLadder=null;
Queue q = new ArrayDeque();
q.add(endLadder);//Here we look from end to start because we need to
reverse the output
int count=1,len = start.length(); //count the number of words for
each level
while(!q.isEmpty() && startLadder==null) {
HashMap map = new HashMap();
int cur=0;
for(int i=0;i
Ladder curLadder = q.poll();
for(int j=0;j
of 26 letters
char[] wordChar = curLadder.word.toCharArray();
for(char c='a';c<='z';c++) {
wordChar[j]=c;
String s = new String(wordChar);
if(s.equals(start)) {//found
if(startLadder!=null) startLadder.parentList.add
(curLadder); // if this is not the first time found
else startLadder = new Ladder(start, curLadder);
}
else if(dict.contains(s) && !s.equals(curLadder.word
)) {//filter those not in dict
Ladder newLadder = new Ladder(s,curLadder);
q.add(newLadder);
map.put(s,newLadder);
cur++;// increase the number of nodes of the
next level
dict.remove(s);
}
else if(map.containsKey(s)) map.get(s).parentList.
add(curLadder); //Same level then reuse the revious existing
}
}
}
count=cur;
}
if(startLadder!=null) buildLadders(new ArrayList(),
endLadder, startLadder);
return ladders;
}
public void buildLadders(ArrayList list,Ladder end, Ladder cur) {
list.add(cur.word);
if(cur==end) ladders.add(new ArrayList(list));
else for(Ladder l:cur.parentList) buildLadders(list,end,l);
list.remove(list.size()-1);
}
}
【在 b****z 的大作中提到】 : 代码如下: : 基本思路是,用queue 进行BFS,记录了每个node的parent,找到之后,通过parent来 : recover path。感觉没有任何冗余计算啊!!!为什么过不了? : 谢谢各位!! : import java.util.ArrayList; : import java.util.HashSet; : import java.util.LinkedList; : import java.util.List; : import java.util.Queue; : import java.util.Set;
| m***2 发帖数: 595 | 13 贴块砖,感觉是我见到的最容易理解好记的版本了
而且能够过最新的test (好多解法之前能过,最新的容易Memory超,感觉leetcode的
判断更严格了)
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> result = new ArrayList>();
if (start == null || end == null || start.length() != end.length() |
| dict.size() == 0) {
return result;
}
HashMap> visited = new HashMap
HashSet>();
HashMap level = new HashMap();
Queue queue = new LinkedList();
HashSet path = new HashSet();
visited.put(start,path);
queue.offer(start);
level.put(start,1);
int min = Integer.MAX_VALUE;
dict.remove(start);
dict.add(end);
while (!queue.isEmpty()) {
String str = queue.poll();
for (int i = 0; i < str.length(); i++) {
char original = str.charAt(i);
for (char c = 'a'; c <= 'z'; c++) {
if (c != original) {
String newStr = replace(str,i,c);
if ((dict.contains(newStr) && !visited.containsKey(
newStr))
|| (visited.containsKey(newStr) && level.get(newStr)
> level.get(str))) {
if (visited.containsKey(newStr)) {
visited.get(newStr).add(str);
}
else {
HashSet path1 = new HashSet(
);
visited.put(newStr,path1);
path1.add(str);
level.put(newStr,level.get(str) + 1);
queue.offer(newStr);
}
if (newStr.equals(end)) {
if (level.get(str) < min) {
ArrayList entry = new ArrayList<
String>();
entry.add(end);
result.addAll(back_trace(str,visited,
entry));
min = level.get(str) + 1;
}
}
}
}
}
}
}
return result;
}
private String replace (String s, int i , char c) {
char[] ch = s.toCharArray();
ch[i] = c;
return new String(ch);
}
private ArrayList> back_trace(String s, HashMap
, HashSet> visited, ArrayList path) {
ArrayList> result = new ArrayList
>>();
ArrayList entry = new ArrayList(path);
entry.add(0,s);
if (visited.get(s).size() < 1) {
result.add(entry);
return result;
}
for (String ss: visited.get(s)) {
result.addAll(back_trace(ss,visited,entry));
}
return result;
}
}
【在 b****z 的大作中提到】 : 代码如下: : 基本思路是,用queue 进行BFS,记录了每个node的parent,找到之后,通过parent来 : recover path。感觉没有任何冗余计算啊!!!为什么过不了? : 谢谢各位!! : import java.util.ArrayList; : import java.util.HashSet; : import java.util.LinkedList; : import java.util.List; : import java.util.Queue; : import java.util.Set;
| t*****t 发帖数: 86 | 14 我第一次做也是用了一个类似lz的wrapper class来记录状态然后TLE了,后来发现如果
是要记录之前状态的话可以用level order traversal的思路,queue里面放List<
String>,每次都针对List中最后一个String进行操作。在while循环内部用一
个for循环遍历一整层的节点,这样的话只需要一个HashSet来记录哪些点被访问过用来
去重就好,不需要针对每个路径专门记录。 | d****n 发帖数: 397 | 15 我一开始也没过。但是注意到不是所有parent都要记录。BFS里面同级之间的parent不
要记录,就可以了。
这是我写的python 解法。
#! /usr/bin/python
import collections
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n',
'o','p','q','r','s','t','u','v','w','x','y','z']
dict = dict | set([end])
dict = dict | set([start])
level = 0
leveldict = {}
q = collections.deque()
q.append((start, level))
parent = {}
level = 0
leveldict = {}
parent[start] = []
visited = {}
leveldict[start] = 0
for s in dict:
visited[s] = 'W'
# BFS to build parent list
while q:
(s, level) = q.popleft()
visited[s] = 'D'
if s == end:
break
l = len(s)
for i in range(l):
for c in alphabet:
if s[i] != c:
stemp = s[:i] + c + s[i + 1:]
if stemp in dict and visited[stemp] == 'W': # if
first time see the node
visited[stemp] = 'G' # color the node as gray
q.append((stemp, level + 1)) # push the node
and its level to the queue parent[stemp] = [s] #
record its parent node leveldict[stemp] = level +
1 # record its level elif stemp in dict and visited[
stemp] == 'G': # if seen it again, but it is not finished (colored as black
if leveldict[stemp] == leveldict[s] + 1: # if its
level is one level more than the current level
parent[stemp].append(s) # add its new parent to its parentlist
else:
pass
# finish building parent list
return self.findLadders_dfs(start, end, parent)
def findLadders_dfs(self, start, end, parent):
'''DFS to get the path'''
if start == end:
return [[end]] # if start equals end, the path just contains one
element
res = []
if end in parent: # if end has parent
for p in parent[end]: # iterate through its parent
subres = self.findLadders_dfs(start, p, parent) #recursively
solve the smaller problem
for list in subres:
res.append(list + [end]) # concatenate to solve the
original problem
return res
【在 b****z 的大作中提到】 : 代码如下: : 基本思路是,用queue 进行BFS,记录了每个node的parent,找到之后,通过parent来 : recover path。感觉没有任何冗余计算啊!!!为什么过不了? : 谢谢各位!! : import java.util.ArrayList; : import java.util.HashSet; : import java.util.LinkedList; : import java.util.List; : import java.util.Queue; : import java.util.Set;
|
|