w***y
发帖数: 6251 | 1 去年面试被问到的hehe 一直不知道到底该怎么做
题目是 Write code to compute the shortest unique prefix of each word in a
set of words.
给的例子是：
譬如如果apple, bee, cat这三个词， 那找到的shortest unique prefix 就是｛a/b/c
｝; 如果是apple bee cat cedar, 就需要 {a/b/ca/ ce} |
s*******s
发帖数: 1031 | 2 用Trie，对apple bee cat cedar,
(node)
a/ b| c\
.... ... (node)
a/ \e
... ...
所以结果是{a/b/ca/ ce} |
s*****n
发帖数: 5488 | 3 looks like it should be a trie: prefix tree
root
a b c
p e a e
p e t d
l a
e r
for each path with one leaf node, it is a unique prefix.
so, dfs, if node.childcount = 1; stop, output the visited nodes.
that is the algo.
/c
【在 w***y 的大作中提到】
: 去年面试被问到的hehe 一直不知道到底该怎么做
: 题目是 Write code to compute the shortest unique prefix of each word in a
: set of words.
: 给的例子是：
: 譬如如果apple, bee, cat这三个词， 那找到的shortest unique prefix 就是｛a/b/c
: ｝; 如果是apple bee cat cedar, 就需要 {a/b/ca/ ce}
|
w***y
发帖数: 6251 | 4 ic
多谢指点迷津啊，我也想到用trie，但是不知道怎么判断是不是到了leaf紧挨着的上面
一层。 其实看node.childcount 就知道了hehe
【在 s*****n 的大作中提到】
: looks like it should be a trie: prefix tree
: root
: a b c
: p e a e
: p e t d
: l a
: e r
: for each path with one leaf node, it is a unique prefix.
: so, dfs, if node.childcount = 1; stop, output the visited nodes.
: that is the algo.
|
t******f
发帖数: 79 | |
w***y
发帖数: 6251 | 6 我想这个题目的要求不是要实现prefix 怎么 insert之类的
如果现在让我重新做这个题目，我会定义一下tree node， 然后介绍一下create tree
的思路。 最后要求实现的这个，应该是基于tree traversal的
【在 t******f 的大作中提到】
: 写code怎么实现prefix tree呢？
|
t******f
发帖数: 79 | 7 有道理啊
tree
【在 w***y 的大作中提到】
: 我想这个题目的要求不是要实现prefix 怎么 insert之类的
: 如果现在让我重新做这个题目，我会定义一下tree node， 然后介绍一下create tree
: 的思路。 最后要求实现的这个，应该是基于tree traversal的
|
z*******3
发帖数: 13709 | 8 这个好，比楼上的要容易实现
【在 s*****n 的大作中提到】
: looks like it should be a trie: prefix tree
: root
: a b c
: p e a e
: p e t d
: l a
: e r
: for each path with one leaf node, it is a unique prefix.
: so, dfs, if node.childcount = 1; stop, output the visited nodes.
: that is the algo.
|
l***a
发帖数: 519 | 9 看来我想的太简单暴力了
我就打算排个序
遇见重复的就再比一下就完了 |
