word ladder 时间空间复杂度是多少, bfs 解的 - JobHunting版

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

JobHunting版 - word ladder 时间空间复杂度是多少, bfs 解的

相关主题
● Word Ladder 这样写时间空间复杂度是多少? 谢谢	● leetcode 129
● 请假大家一道BB的题	● word ladder ii 谁给个大oj不超时的？
● leetcode 上 wordladderII 求教	● 被G电面给毙了
● 请教word ladder\| \|	● leetcode number of islands为什么不能用BFS？
● 一道电面题，分享下，这个题应该用哪几个data structure?	● 诡异的number of islands.
● 杯具！越改越差	● 微软有组在招new grad software engineer吗？
● WordLadderII 看到很多解法比较长。抛砖引玉，求更简洁解法。	● Word ladder II 感觉算法已经是最优了，但是过不了大测试，能不能帮忙看看？
● 贡献一道G家的面试题	● 这段word ladder II怎么改？

相关话题的讨论汇总
话题: string话题: hashset话题: cur话题: beginword话题: int

进入JobHunting版参与讨论

(共1页)

f****e
发帖数: 923

网上的搜索的众说纷纭
https://goo.gl/ebfvvD
public class Solution {
public int ladderLength(String beginWord, String endWord, List
wordList) {
Queue q = new LinkedList<>();
HashSet list = new HashSet<>(wordList);
int level = 0;
q.add(beginWord);
HashSet set = new HashSet<>();
set.add(beginWord);
while(!q.isEmpty()){
int size = q.size();
level++;
for(int i = 0; i < size; i++){
char[] cur = q.remove().toCharArray();
for(int j = 0; j < cur.length; j++){
char temp = cur[j];
for(char c = 'a'; c <= 'z'; c++){
cur[j] = c;
String next = new String(cur);
if(list.contains(next)){
if(next.equals(endWord)){
return level + 1;
}else if(!set.contains(next)){
q.add(next);
set.add(next);
}
}
}
cur[j] = temp;
}
}
}
return 0;
}
}

(共1页)

进入JobHunting版参与讨论

相关主题
● 这段word ladder II怎么改？	● 一道电面题，分享下，这个题应该用哪几个data structure?
● 不明白leetcode OJ wordladder 2 总是 Time Limit Exceeded	● 杯具！越改越差
● 有人面试遇到word-ladder-ii这道题目吗？	● WordLadderII 看到很多解法比较长。抛砖引玉，求更简洁解法。
● word ladder能只用一个queue搞定吗？	● 贡献一道G家的面试题
● Word Ladder 这样写时间空间复杂度是多少? 谢谢	● leetcode 129
● 请假大家一道BB的题	● word ladder ii 谁给个大oj不超时的？
● leetcode 上 wordladderII 求教	● 被G电面给毙了
● 请教word ladder\| \|	● leetcode number of islands为什么不能用BFS？

相关话题的讨论汇总
话题: string话题: hashset话题: cur话题: beginword话题: int

#	版面	帖数(主题数)
-	全站	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日

历史上的今天