Word ladder II 感觉算法已经是最优了，但是过不了大测试，能不能帮忙看看？ - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - Word ladder II 感觉算法已经是最优了，但是过不了大测试，能不能帮忙看看？

相关主题
● leetcode 上 wordladderII 求教	● 问个java hashcode的题
● 微软有组在招new grad software engineer吗？	● [面试题求教]remove common phrases from each sentence
● word ladder ii 谁给个大oj不超时的？	● 谁能给贴个大数相减的java code 吗？
● WordLadderII 看到很多解法比较长。抛砖引玉，求更简洁解法。	● 贡献G家电面面经
● leetcode出了新题word ladder	● 问一个facebook的电面
● 这段word ladder II怎么改？	● 50行code能解决addbinary 问题么
● 不明白leetcode OJ wordladder 2 总是 Time Limit Exceeded	● 问下LeetCode上的题目：count and say
● 一道电面题，分享下，这个题应该用哪几个data structure?	● 星期一福利：某公司店面题

相关话题的讨论汇总
话题: string话题: list话题: wrapper话题: arraylist话题: ladder

进入JobHunting版参与讨论

(共1页)

b****z
发帖数: 176

代码如下：
基本思路是，用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

TLE?我的也是，不同的版本，一个几周前过了，一个昨天的就没有。你可一先local
debug 一下。。。

P*******L
发帖数: 2637

这个题用 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

本地都是对的。但是不知道为什么过不了大数据

【在 a******l 的大作中提到】

: TLE?我的也是，不同的版本，一个几周前过了，一个昨天的就没有。你可一先local
: debug 一下。。。

b****z
发帖数: 176

但是也看到有人 java过得，所以想问问是不是自己算法有问题

【在 P*******L 的大作中提到】

: 这个题用 Java 写很难过，但同样的算法 C++ 过很容易。

A****L
发帖数: 138

这个事我以前开的帖子。
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 的大作中提到】

b****z
发帖数: 176

a******l
发帖数: 72

TLE?我的也是，不同的版本，一个几周前过了，一个昨天的就没有。你可一先local
debug 一下。。。

P*******L
发帖数: 2637

这个题用 Java 写很难过，但同样的算法 C++ 过很容易。

【在 b****z 的大作中提到】

b****z
发帖数: 176

本地都是对的。但是不知道为什么过不了大数据

【在 a******l 的大作中提到】

: TLE?我的也是，不同的版本，一个几周前过了，一个昨天的就没有。你可一先local
: debug 一下。。。

相关主题
● 这段word ladder II怎么改？	● 问个java hashcode的题
● 不明白leetcode OJ wordladder 2 总是 Time Limit Exceeded	● [面试题求教]remove common phrases from each sentence
● 一道电面题，分享下，这个题应该用哪几个data structure?	● 谁能给贴个大数相减的java code 吗？
进入JobHunting版参与讨论

b****z
发帖数: 176

但是也看到有人 java过得，所以想问问是不是自己算法有问题

【在 P*******L 的大作中提到】

: 这个题用 Java 写很难过，但同样的算法 C++ 过很容易。

A****L
发帖数: 138

m***2
发帖数: 595

贴块砖，感觉是我见到的最容易理解好记的版本了
而且能够过最新的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 的大作中提到】

t*****t
发帖数: 86

我第一次做也是用了一个类似lz的wrapper class来记录状态然后TLE了，后来发现如果
是要记录之前状态的话可以用level order traversal的思路，queue里面放List<
String>，每次都针对List中最后一个String进行操作。在while循环内部用一
个for循环遍历一整层的节点，这样的话只需要一个HashSet来记录哪些点被访问过用来
去重就好，不需要针对每个路径专门记录。

d****n
发帖数: 397

我一开始也没过。但是注意到不是所有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 的大作中提到】

(共1页)

进入JobHunting版参与讨论

相关主题
● 星期一福利：某公司店面题	● leetcode出了新题word ladder
● 请教一道G的电面题。。	● 这段word ladder II怎么改？
● text justification 有人ac吗	● 不明白leetcode OJ wordladder 2 总是 Time Limit Exceeded
● Leetcode word ladder 求助！	● 一道电面题，分享下，这个题应该用哪几个data structure?
● leetcode 上 wordladderII 求教	● 问个java hashcode的题
● 微软有组在招new grad software engineer吗？	● [面试题求教]remove common phrases from each sentence
● word ladder ii 谁给个大oj不超时的？	● 谁能给贴个大数相减的java code 吗？
● WordLadderII 看到很多解法比较长。抛砖引玉，求更简洁解法。	● 贡献G家电面面经

相关话题的讨论汇总
话题: string话题: list话题: wrapper话题: arraylist话题: ladder

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天