t*******2
发帖数: 182 | 1 Given a set of strings, return the smallest subset that contains prefixes
for every string.
If the list is ['foo', 'foog', 'food', 'asdf'] return ['foo', 'asdf'] |
b******i
发帖数: 914 | 2 为什么不是返回['f', 'a']呢？是要求返回的subset里面没个元素要是原来的set的
string吗？
大概的思路就是：
1. 先对原来的list建一个trie
2. 从trie的root开始做BFS，有非空的child就往下走，直到找到第一个是词的child，
在这
个过程中把path放到result中
【在 t*******2 的大作中提到】
: Given a set of strings, return the smallest subset that contains prefixes
: for every string.
: If the list is ['foo', 'foog', 'food', 'asdf'] return ['foo', 'asdf']
|
z******y
发帖数: 444 | 3
list很长且prefix多的时候，会很多棵树，效率很低吧...不过也想不出更好的办法
【在 b******i 的大作中提到】
: 为什么不是返回['f', 'a']呢？是要求返回的subset里面没个元素要是原来的set的
: string吗？
: 大概的思路就是：
: 1. 先对原来的list建一个trie
: 2. 从trie的root开始做BFS，有非空的child就往下走，直到找到第一个是词的child，
: 在这
: 个过程中把path放到result中
|
c******n
发帖数: 4965 | 4 题目定义不清楚，
你说得对， 照它现在这样说， 就是看所有string 最头的一个字母有多少uniq 的
【在 b******i 的大作中提到】
: 为什么不是返回['f', 'a']呢？是要求返回的subset里面没个元素要是原来的set的
: string吗？
: 大概的思路就是：
: 1. 先对原来的list建一个trie
: 2. 从trie的root开始做BFS，有非空的child就往下走，直到找到第一个是词的child，
: 在这
: 个过程中把path放到result中
|
d******e
发帖数: 2265 | 5 trie可以但是是ovekill.
简单的用sort，然后下面写个isprefixhelper func。小量这个简单的很。
note that
A is prefix or b, b is prefix of C means, A --> C.
so after sort, it is o(n) computation.
【在 b******i 的大作中提到】
: 为什么不是返回['f', 'a']呢？是要求返回的subset里面没个元素要是原来的set的
: string吗？
: 大概的思路就是：
: 1. 先对原来的list建一个trie
: 2. 从trie的root开始做BFS，有非空的child就往下走，直到找到第一个是词的child，
: 在这
: 个过程中把path放到result中
|
P******r
发帖数: 1342 | 6 建trie的复杂度是多少？sort呢？
：trie可以但是是ovekill.
：简单的用sort，然后下面写个isprefixhelper func。小量这个简单的很。 |
d******e
发帖数: 2265 | 7 你不要光看复杂度。你写一个trie放product里面出 bug的概率多少？你申请那么多内
存代价是多少？你几天能出活？你要写多少test code?
老实用内建的优化的sort, in place 可以搞定所有的问题。
至于复杂度，我可以告诉你大多数情况python内置的timsort是o(n)。
光刷题出来的，什么都自己搞的，公司敢用嘛？
【在 P******r 的大作中提到】
: 建trie的复杂度是多少？sort呢？
:
: ：trie可以但是是ovekill.
: ：简单的用sort，然后下面写个isprefixhelper func。小量这个简单的很。
|
z***y
发帖数: 73 | 8 啊，好像没那么复杂吧。
trie和sort肯定都可以啦。
简单点就是遍历一遍，按照第一个字母分类。
然后遍历每一类，从第二个字母检查是否都一样，碰到末尾就说明结束了。 |
