Z**********4
发帖数: 528 | 1 有快的思路嘛？
本来想着按照字母顺序做inverted index，这样找没有相同字母的string就是集合操作
了。
不过好像还是很傻逼这个办法。 |
y***n
发帖数: 1594 | 2 有没有肯能用list of words 先做个Trie？ |
Z**********4
发帖数: 528 | 3 感觉这里trie不是特别好使？
【在 y***n 的大作中提到】
: 有没有肯能用list of words 先做个Trie？
|
T*****u
发帖数: 7103 | 4 把string按长度大到小排序，从最长string开始,index = 0，往回搜符合条件的，停止
在index i，剩下的全扔掉，然后从index = 1开始，搜到新的list到index j，找到或
者找不到比length(t)*length(s)更长的，recursion 到 list没有了？ |
c*******y
发帖数: 98 | 5 我认为做trie可行。
找每个单词缺set，排序，建trie
Root->｛缺a，缺b, ...}
Root->缺a->｛缺a，缺b, ...}
最多26层
对每一个单词的set，排序以后按trie查找，能找到全部set才行。然后return最高的节
点。
似乎是O n
【在 y***n 的大作中提到】
: 有没有肯能用list of words 先做个Trie？
|
Z**********4
发帖数: 528 | 6 看的不是特别明白 展开说说？
【在 c*******y 的大作中提到】
: 我认为做trie可行。
: 找每个单词缺set，排序，建trie
: Root->｛缺a，缺b, ...}
: Root->缺a->｛缺a，缺b, ...}
: 最多26层
: 对每一个单词的set，排序以后按trie查找，能找到全部set才行。然后return最高的节
: 点。
: 似乎是O n
|
T*****u
发帖数: 7103 | 7 每个string都vectorize到a-z，然后算tanimoto coefficient，0的就是没有over lap
的。
【在 T*****u 的大作中提到】
: 把string按长度大到小排序，从最长string开始,index = 0，往回搜符合条件的，停止
: 在index i，剩下的全扔掉，然后从index = 1开始，搜到新的list到index j，找到或
: 者找不到比length(t)*length(s)更长的，recursion 到 list没有了？
|
y****n
发帖数: 743 | 8 26个字母，每个字母的出现情况，可以映射成一个32bit整数。
那么每个单词都会很快生成一个标记码。使用位运算来判断是否两个单词有相同字母。
空间O(n)，时间O(n^2)
优化可以考虑：对单词长度分组，如果已经找到某长度的组合则跳过更短的单词组。 |
y***n
发帖数: 1594 | 9 感觉这个可行。
【在 y****n 的大作中提到】
: 26个字母，每个字母的出现情况，可以映射成一个32bit整数。
: 那么每个单词都会很快生成一个标记码。使用位运算来判断是否两个单词有相同字母。
: 空间O(n)，时间O(n^2)
: 优化可以考虑：对单词长度分组，如果已经找到某长度的组合则跳过更短的单词组。
|
m********6
发帖数: 58 | 10 The set for each word is O(n!)
我认为做trie可行。找每个单词缺set，排序，建trieRoot-
【在 c*******y 的大作中提到】
: 我认为做trie可行。
: 找每个单词缺set，排序，建trie
: Root->｛缺a，缺b, ...}
: Root->缺a->｛缺a，缺b, ...}
: 最多26层
: 对每一个单词的set，排序以后按trie查找，能找到全部set才行。然后return最高的节
: 点。
: 似乎是O n
|
n*****7
发帖数: 154 | 11 有个问题是string只能有一个word 还是可以有很多word |
