j******s
发帖数: 48 | 1 Hi,请问word ladder II 的测试数据是不有点问题么？
对于输入:
"hit", "cog", ["hot","cog","dot","dog","hit","lot","log"]
我的输出是
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"],["hot","dot
","lot","log","cog"],["hot","dot","dog","log","cog"]]
测试数据输出的是
[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
根据题目的定义应该是都可以的吧？
嗯嗯，我知道答案是不是正确不是特别重要，只是这道题我花了很多时间对比BFS,DFS,
IDS以及实现他们的一些不同方式，所以希望可以求证一下而已。
附贴上我的代码
class Solution {
private:
class Node{
public:
string word;
vector阅读全帖 |
|
r**********1
发帖数: 13 | 2 DP可以这样做吧，就是给定个单词，在其左右不停添加新字母（a-z，26个），看新单
词在不在字典里，取最大长度
int findlongest(string W[], int n){
先建个hashtable包含所有单词
int longest = 0;
for i=1 to n //扫描每个单词
{
string w = W[i]; //当前的单词
int t = 1+max(furthertest(W[i], 0), furthertest(W[i], 1));
longest = max(t, longest);
}
return longest;
}
int furthertest(string s, bool tryleft)
{
int maxcount = 0;
if (tryleft) //if tryleft==1, 往左边添
{
for (int i=0; i < 26; ++i)
{
string newword(1, i+'a');
... 阅读全帖 |
|
t********n
发帖数: 611 | 3 还是不够快的问题，自己机器上测试结果正确，用了BFS and DFS，不知道还能怎样改
进，请牛牛们指教！
Python code:
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):
def buildPath(end, start, path= []):
path += [end]
if end == start:
path.reverse()
result.append(path)
else:
for p in parents[end]:
... 阅读全帖 |
|
t********n
发帖数: 611 | 4 用的bfs， 总是得到TLE结果。请问还有什么办法可以更快？谢谢！
Python code :
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return an integer
def ladderLength(self, start, end, d):
d = set(d)
q = []
dis = {}
dis[start] = 1
q.append(start)
letters = string.letters[0:26]
while q !=[]:
x = q.pop()
# print x
for i in range(len(x)):
... 阅读全帖 |
|
t********n
发帖数: 611 | 5 过了， 参考了某位高人的代码，每次找下级词汇前，把这一级从字典里删除，立刻快
了很多。
Code:
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):
def buildPath(end, start, path= []):
# print
# print "path at beginning:", path
path += [end]
if end == start:
path.reverse()
result.append(path)
else:
... 阅读全帖 |
|
s****a
发帖数: 528 | 6 1. build hash table for words in : wordsSet
2. sort the words from shortest to longest: wordsArray
while(!wordsArray.empty())
{
string word = wordsArray.back();
wordsArray.pop_back();
int maxLength = word.length();
if (maxLength == 1) return 1;
if (wordsSet.find(word) == wordsSet.end())
continue; // this word is already tested
wordsSet.erase(word);
WordsStack subWordsStack;
subWordsStack.push(word);
// check if the word can be build up from 1 to maxle... 阅读全帖 |
|
s****a
发帖数: 528 | 7 1. build hash table for words in : wordsSet
2. sort the words from shortest to longest: wordsArray
while(!wordsArray.empty())
{
string word = wordsArray.back();
wordsArray.pop_back();
int maxLength = word.length();
if (maxLength == 1) return 1;
if (wordsSet.find(word) == wordsSet.end())
continue; // this word is already tested
wordsSet.erase(word);
WordsStack subWordsStack;
subWordsStack.push(word);
// check if the word can be build up from 1 to maxle... 阅读全帖 |
|
z*********e
发帖数: 10149 | 8 现在会超时，哪个地方应该优化一下？用的BFS
本机上一秒之内就出结果了，应该没有严重的算法问题吧
public List> findLadders(String start, String end, Set
dict) {
List> lastPaths = new ArrayList<>();
if(start == null || end == null) return lastPaths;
dict.add(end);
List top = new ArrayList<>();
top.add(start);
lastPaths.add(top);
if(start.equals(end)) return lastPaths;
int wordLen = start.length();
while(!dict.isEmpty()){ // same as ... 阅读全帖 |
|
w*s
发帖数: 7227 | 9 i read 4 bytes from a file,
say it's 88130000 in the hex format,
now i want to pack it to 0x00001388 which is 5000 dex.
so basically how to convert 0x88130000 into 5000 (0x00001388).
my code is like this, way to complicated.
$bytes = read($fh, $buf, 4);
$word = unpack 'H*', $buf;
print $word."\n";
($d2,$d3,$d0,$d1) = unpack("b8 b8 b8 b8", $word);
$newWord = pack("... 阅读全帖 |
|
D********g
发帖数: 650 | 10 第二题，我的code，主要算法是recursion + memoization，有没有人能分析一下这个
算法的复杂度？
static String findLongestDecomposableWord(Set dict) {
String longest = null;
Set mem = new HashSet();
for (String word : dict) {
if (findLongestDecomposableWordInternal(word, mem, dict)) {
if (longest == null || word.length() > longest.length()) {
longest = word;
}
}
}
return longest;
}
... 阅读全帖 |
|
S*******C
发帖数: 822 | 11 Input: WORD.LST
And a randomly picked 1000 words from the same WORD.LST for querying.
This is a list of > 100,000 English words. It is sorted alphabetically.
Your task is to create a Compact Trie. Each node of trie will contain,
(1) A leading character (possibly empty (for root))
(2) String Label (possibly null (for root))
(3) Boolean IsWord , indicating whether the current node represents a whole
word or not (this is helpful when one word may be a prefix of another).
(4) Node *RightSIbling
(5)... 阅读全帖 |
|
S*******C
发帖数: 822 | 12 Input: WORD.LST
And a randomly picked 1000 words from the same WORD.LST for querying.
This is a list of > 100,000 English words. It is sorted alphabetically.
Your task is to create a Compact Trie. Each node of trie will contain,
(1) A leading character (possibly empty (for root))
(2) String Label (possibly null (for root))
(3) Boolean IsWord , indicating whether the current node represents a whole
word or not (this is helpful when one word may be a prefix of another).
(4) Node *RightSIbling
(5)... 阅读全帖 |
|
m**e
发帖数: 150 | 13 猜测可能的问题
1.if 后面没有换行
2.第45行太长，应该分行写。
3.第45行应该是words.Contains(newWord)?
4.current, next名字不好，换成currentLevelWords, nextLevelWords?
5. c#? 用固定的type int, string 也许比var好。你在里面混用，风格不统一。
6. line 28 29 可以合并
其实那么短的时间写出来真是不错，稍微注意一下格式应该就过了。 |
|
j********r
发帖数: 127 | 14 这题现场写是很繁琐。
你有一个typo: words.contains(newword)
另外如果是双向找就会效率高很多，单向找leetcode现在过不了了 |
|
S********t
发帖数: 3431 | 15 你找出来的这些大部分都是nit吧.
简单做个code review
1) really should use queue instead of hashset;
2) you are essentially doing level-by-level bfs, which is not wrong but
unnecessary
3) should mark visited instead of removing from dictionary, ususally input
dictionary is supposed to be immutable. PS., I think most ppl get spoiled by
leetcode's function signatures that allows you to modify input data in
place.
4) newWord is unnecessary, just change the char in place and change back to
'temp'
5) return immediately ... 阅读全帖 |
|
v********h
发帖数: 10 | 16 这是c#，猜测期望是两边选少的交换着BFS,效率要高不少,而且newWord可以直接判断是
不是target,不用都扫遍了再找，string转char array再转回string开销大，有优化的
余地，可能要提提，跟c比起来，c#开销不知道要差多少 |
|
d******n
发帖数: 3014 | 17 原文刊载在dc.watch.impress.co.jp上
http://dc.watch.impress.co.jp/docs/news/20120810_551672.html
引用、转载请注意尊重原文的版权
****************************************上篇********************************
*************************
佳能于9月中旬推出可更换镜头的数码相机EOS M，这是该公司第一个无反光镜相机，因
此受到公众瞩目。我们就EOS M的技术特征以及产品战略请教了佳能公司。这次接受我
们采访的成员，是佳能图像通讯事业总部ICP第二事业部部长户仓刚先生（负责EOS M的
产品规划）、该ICP第二开发中心室长菊池裕先生（负责机械设计部分、以及EOS M整体
设计的协调）、综合设计中心专任主任鸣鸟英树先生（图像用户界面的负责人）、综合
设计中心专任主任川岛昭作先生（外观设计负责人）、以及该ICP第一事业部代理科长
中村裕先生（负责EF-M镜头的产品规划）。
■主要目标客户群为“相机女”
无反机的目标... 阅读全帖 |
|
t****1
发帖数: 4 | 18 来自主题: ChineseClassics版 - 汉字的密码 说得不错！
另外，汉字具有收敛性，有限的汉字理论上可以组合表达无穷多的意思。而西方文字则是
开放性的，出现了新的概念往往要新造字。其最直接的后果就是新字越来越多。举个例子
，AUDIOPHILE, 是个最近发明的新名词，表示 One who loves and collects audio
equipment and media，（见http://www.owlnet.rice.edu/~ling215/NewWords/page1.html），用汉字则可以表达为"音像品收集者"，一个生字没有。
汉字的这种相对稳定性，对于学习者来说无疑是一个巨大优点。
此外，斯塔夫里阿诺斯的“全球通史”这本书中还有一个观点。认为，汉字对于中华民族
的团结和稳定也起了非常大的作用。其论据为，虽然中国各地方言往往南辕北辙，但却都
懂得同一种书面语。其根本在于汉字是表意字，也就是说，一个汉字写出来，虽然不同的
方言有不同的读法，但意思却完全相同。另一方面，西方文字则是表音不表意，发音不同
，写法则不一。比如说 8 这个字，在中国虽然各地读法大不相同，写出来的方式却只有
一种，即“八”。而在欧洲，意大利，瑞典 |
|
