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 |