j***t 发帖数: 50 | 1 How to solve this problem? what algorithm should be used?
For a list of strings, find the largest subsets, within it, no string is a
prefix of another one.
For example,
a, abc, acd, df, dfe
The largets sub sets would be (both are of size 3):
abc, acd, def
or
abc acd, dfe
| x******3 发帖数: 245 | 2 把所有string放在一个trie里,用一个sentinel作trie的根节点
然后把所有叶子拿出来,就是要的解 | B*****t 发帖数: 335 | 3 how about topological sort
string is a
【在 j***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : How to solve this problem? what algorithm should be used? : For a list of strings, find the largest subsets, within it, no string is a : prefix of another one. : For example, : a, abc, acd, df, dfe : The largets sub sets would be (both are of size 3): : abc, acd, def : or : abc acd, dfe :
| l*******e 发帖数: 309 | | x******3 发帖数: 245 | 5 每个字母作一个节点吗
【在 B*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : how about topological sort : : string is a
| B*****t 发帖数: 335 | 6 每个单词作一个节点
【在 x******3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每个字母作一个节点吗
| x******3 发帖数: 245 | 7 具体说下吧,不是很理解怎么用
【在 B*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每个单词作一个节点
| B*****t 发帖数: 335 | 8 1. 删除重复字串.
2. 建立一个DAG,比如, 如果两个单词有prefix的关系的话,建立一条有向边。
3. 统计入度为0的节点。
建图的时候可以先sort一下,worst case复杂度O(n^2)
【在 x******3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 具体说下吧,不是很理解怎么用
| B*****i 发帖数: 831 | 9 within the subset no string is the prefix of another one
是不是要先找一下weakly connected component,然后分别取最大的那部分啊? | B*****t 发帖数: 335 | 10 突然发现一点儿问题
string is a
===================================
这里的def是怎么来的?!!!
===================================
【在 j***t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : How to solve this problem? what algorithm should be used? : For a list of strings, find the largest subsets, within it, no string is a : prefix of another one. : For example, : a, abc, acd, df, dfe : The largets sub sets would be (both are of size 3): : abc, acd, def : or : abc acd, dfe :
| k*n 发帖数: 150 | 11 cool!
【在 x******3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把所有string放在一个trie里,用一个sentinel作trie的根节点 : 然后把所有叶子拿出来,就是要的解
|
|