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
|
