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 的大作中提到】
: 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 的大作中提到】
: how about topological sort
:
: string is a
| B*****t
发帖数: 335 | 6 每个单词作一个节点
【在 x******3 的大作中提到】
: 每个字母作一个节点吗
| x******3
发帖数: 245 | 7 具体说下吧，不是很理解怎么用
【在 B*****t 的大作中提到】
: 每个单词作一个节点
| B*****t
发帖数: 335 | 8 1. 删除重复字串.
2. 建立一个DAG，比如, 如果两个单词有prefix的关系的话，建立一条有向边。
3. 统计入度为0的节点。
建图的时候可以先sort一下，worst case复杂度O(n^2)
【在 x******3 的大作中提到】
: 具体说下吧，不是很理解怎么用
| 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 的大作中提到】
: 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 的大作中提到】
: 把所有string放在一个trie里，用一个sentinel作trie的根节点
: 然后把所有叶子拿出来，就是要的解
|
|
