B*******1 发帖数: 2454 | 1 careercup上面看到的,g得phone interiview
Suppose you are given a dictionary of words based on an alphabet with a
fixed number of characters. Please write a method / function which will find
the longest word in the dictionary such that it can be built from
successively adding a single character to an existing word in the dictionary
(in any location). For instance, "a" -> "at" -> "cat" -> "chat" -> "chart". |
t***s 发帖数: 602 | 2 介个是trie?
find
dictionary
".
【在 B*******1 的大作中提到】 : careercup上面看到的,g得phone interiview : Suppose you are given a dictionary of words based on an alphabet with a : fixed number of characters. Please write a method / function which will find : the longest word in the dictionary such that it can be built from : successively adding a single character to an existing word in the dictionary : (in any location). For instance, "a" -> "at" -> "cat" -> "chat" -> "chart".
|
d*******d 发帖数: 2050 | 3 trie 里面找最深节点,path上每个点都是个词。
【在 B*******1 的大作中提到】 : careercup上面看到的,g得phone interiview : Suppose you are given a dictionary of words based on an alphabet with a : fixed number of characters. Please write a method / function which will find : the longest word in the dictionary such that it can be built from : successively adding a single character to an existing word in the dictionary : (in any location). For instance, "a" -> "at" -> "cat" -> "chat" -> "chart".
|
v*****k 发帖数: 7798 | 4 不行吧,at->cat不在一条path上
【在 d*******d 的大作中提到】 : trie 里面找最深节点,path上每个点都是个词。
|
d*******d 发帖数: 2050 | 5 哦,我题目没看仔细。
那就用hashset.
【在 v*****k 的大作中提到】 : 不行吧,at->cat不在一条path上
|
b*******y 发帖数: 232 | 6 有向图,从原点(一个字母开始)找最长的path?
find
dictionary
".
【在 B*******1 的大作中提到】 : careercup上面看到的,g得phone interiview : Suppose you are given a dictionary of words based on an alphabet with a : fixed number of characters. Please write a method / function which will find : the longest word in the dictionary such that it can be built from : successively adding a single character to an existing word in the dictionary : (in any location). For instance, "a" -> "at" -> "cat" -> "chat" -> "chart".
|
B*******1 发帖数: 2454 | 7 我也是这么想的,建立一个图 ,但是觉得不是最优的。 |
g**********y 发帖数: 14569 | 8 1. 把字典按字长分进数组
2. 单字 -> map[1](key, "")
3. 从 i = 2 开始循环,找长度为 i, 减去一个字母后在map[i-1]的keySet里的单词,
放进map[i](key, shrinked)
4. 重复3,直到map[i]为空。
从map[i-1]任挑一个就是最长的可变化的词。英语里好象就一个解: carrousel.
carrousel - carousel - carouse - arouse - rouse - ruse - use - us - s
用本更大的字典找的:
complecting - completing - competing - compting - comping - coping - oping - ping - pig - pi - i |
a**********2 发帖数: 340 | |
r*****n 发帖数: 20 | 10 http://www.mediafire.com/?djzgrn1eong
找到了如下chain:
abranchiate -- 无鳃动物
abranchiate-branchiate-branchiae-branchia-branchi-branch-ranch-rach-ach-ah-h
全是些诡异单词 不知道这是个啥dic。。。
和gloomyturkey的结果一样 这个chain长11 |
g*****i 发帖数: 2162 | 11 你的方法是从短的到长的.
从长到短效率相比之下如何? 对一个长词,如果发现最后不能分解,那么一路上所有的变
种都可以不在考虑了
- ping - pig - pi - i
【在 g**********y 的大作中提到】 : 1. 把字典按字长分进数组 : 2. 单字 -> map[1](key, "") : 3. 从 i = 2 开始循环,找长度为 i, 减去一个字母后在map[i-1]的keySet里的单词, : 放进map[i](key, shrinked) : 4. 重复3,直到map[i]为空。 : 从map[i-1]任挑一个就是最长的可变化的词。英语里好象就一个解: carrousel. : carrousel - carousel - carouse - arouse - rouse - ruse - use - us - s : 用本更大的字典找的: : complecting - completing - competing - compting - comping - coping - oping - ping - pig - pi - i
|
m**q 发帖数: 189 | 12 考个古。火鸡的思路很不错,保证了每次在寻找长度为i+1词的时候,
长度为i的有效词都已经计算出来了,只需要查找这些有效词,类似
于DP。
我觉得从长到短会有很多的重复计算,当然也可以用记事本的方法
不过空间开销比较大
【在 g*****i 的大作中提到】 : 你的方法是从短的到长的. : 从长到短效率相比之下如何? 对一个长词,如果发现最后不能分解,那么一路上所有的变 : 种都可以不在考虑了 : : - ping - pig - pi - i
|