l****1
发帖数: 33 | 1 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
并且满足word1和word2没有common letter. |
h*********a
发帖数: 1605 | |
A*********c
发帖数: 430 | 3 先把所有的单词排序得出anagram，因为单词不长，可以算constant，这步O(n)
然后再比较common letter是不是会好点，可以early stop。这步有没有比暴力更好的
方法？
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
|
f*****e
发帖数: 2992 | 4 用map
每个string用一个整数表示, 然后第二个表示max length。
判断两个string 是否相交，就为 i & j == 0.
在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
【在 A*********c 的大作中提到】
: 先把所有的单词排序得出anagram，因为单词不长，可以算constant，这步O(n)
: 然后再比较common letter是不是会好点，可以early stop。这步有没有比暴力更好的
: 方法？
|
A*********c
发帖数: 430 | 5 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
也可以接受。
感觉比anagram的想法好。
【在 f*****e 的大作中提到】
: 用map
: 每个string用一个整数表示, 然后第二个表示max length。
: 判断两个string 是否相交，就为 i & j == 0.
: 在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
|
M*******a
发帖数: 1633 | |
m**********g
发帖数: 153 | 7 是不是可以build trie, 得到26个子树的高度，然后求max product of the 26 number
? |
M*******a
发帖数: 1633 | 8 恩，这个好，基本O(N*average_length_of_string + 26*26)
number
【在 m**********g 的大作中提到】
: 是不是可以build trie, 得到26个子树的高度，然后求max product of the 26 number
: ?
|
c********p
发帖数: 1969 | |
b***e
发帖数: 1419 | 10 Not working, cannot guarantee disjoint.
【在 M*******a 的大作中提到】
: 恩，这个好，基本O(N*average_length_of_string + 26*26)
:
: number
|
|
|
b***e
发帖数: 1419 | 11 如果N巨大的话，做exponential set pre-computing吧。假设alphabet只有26个字母，
需要64M个4 bytes. 不算太离谱.
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
|
t********e
发帖数: 344 | 12 这样找最长的words可以，但怎么保证没有common char?
number
【在 m**********g 的大作中提到】
: 是不是可以build trie, 得到26个子树的高度，然后求max product of the 26 number
: ?
|
l****1
发帖数: 33 | 13 我用查表来算是否两个单词有common letter, 然后用O(N^2)来比较。估计
过不了电面 |
l****f
发帖数: 6 | |
w********0
发帖数: 377 | 15 能否站看说说如何用一个整数表示一个string，如果string非常长，一个整数的长度一
定会够吗？谢谢。想了很久，没想明白。
【在 f*****e 的大作中提到】
: 用map
: 每个string用一个整数表示, 然后第二个表示max length。
: 判断两个string 是否相交，就为 i & j == 0.
: 在想能不能用二叉树表示，不相交的在左边，相交的在右边。就不知道是否平衡了。
|
w********0
发帖数: 377 | 16 请教如何一个单词用4 byte表示？单词很长，也可以做到吗？谢谢
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
|
f*****e
发帖数: 2992 | 17 就是用一个26bit的数字表示有没有相应的character。
【在 w********0 的大作中提到】
: 能否站看说说如何用一个整数表示一个string，如果string非常长，一个整数的长度一
: 定会够吗？谢谢。想了很久，没想明白。
|
P****d
发帖数: 137 | 18 这个题是C特有的吗？strlen是求字符串长度吗？如果是java是不是直接遍历所有的元
素用word1.length()*word2.length()看最后哪个乘机大就行了是么？有没有共同元素
对求string长度有什么影响吗？
【在 l****1 的大作中提到】
: 假设字典有N个单词，求最大的： product = strlen(word1) * strlen(word2),
: 并且满足word1和word2没有common letter.
|
t**8
发帖数: 4527 | 19 good
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
|
w****a
发帖数: 710 | 20 后来请教了别人，这题可以对字典建后缀树，lca为root的两个叶节点就是没有common
letter的。然后从root找，两条最长的到叶子节点的path就是了。 |
|
|
x****g
发帖数: 1512 | 21 “lca为root的两个叶节点就是没有common : letter的”
这个结论不对？只能判出无公共前缀，而不是无common letter.
common
【在 w****a 的大作中提到】
: 后来请教了别人，这题可以对字典建后缀树，lca为root的两个叶节点就是没有common
: letter的。然后从root找，两条最长的到叶子节点的path就是了。
|
d*****1
发帖数: 263 | |
a**********s
发帖数: 588 | 23 假设有两个string，一个是abc，另一个是b.
你说的suffix tree应该怎样的？
common
【在 w****a 的大作中提到】
: 后来请教了别人，这题可以对字典建后缀树，lca为root的两个叶节点就是没有common
: letter的。然后从root找，两条最长的到叶子节点的path就是了。
|
d*****1
发帖数: 263 | 24 后缀树我没想明白，我是用trie做的。 l 是单词长度。
假如每个单词都排序完毕（O(n * l(lg l))，应该是O(n)的复杂度。
（就是一个单词里，有重复的时候，需要另外处理）
例如 输入是 bbbc, 和bbc 就要另外加东西标识出来。 |
x*******6
发帖数: 262 | 25 后缀树理论建造需要n，再遍历所有internal node，每个internal node应该包含所有
经过这个node的string的信息，这样就能找到所有有common letter的string了。 |
x****g
发帖数: 1512 | 26 需要的是“没有common letter”。
无论字典树或者后缀树对于判定找出无common letter并不优。
将原来的s1....sn用26bit法转化成
A1.....An
对应的最大长度为： V1.....Vn
有两个好处：
1：判定无common letter即为：Ai & Aj == 0;
2：相同bit表示的不同字符串得到压缩，只需要记下长度最长的。
完了按Vn长度排序 N*Log(N)
V'n........V'1
A'n........A'1
从大到小搜索，如果Ai & Aj==0的话，L=V[i]*V[j].
那么大的那个下标就收缩到了k,V[k]>sqrt(L).
整体区间收缩到[l,r]满足
V[i]>V[l]
V[r]>V[j]
平均复杂度能N*Log(N)? ,最差当然还是N^2.
i =0;
j = n;
maxLen = 0;
highLen = INT_MAX;
lowLen = INT_MIN;
while(V[i]>sqrt(maxLen) && (i
{
if(V[i] < highLen)
{
for(int k=i+1;klowLen;k++)
{
if(A[i] & A[k]==0)
{
maxLen=max(maxLen,V[i]*V[k]);
lowLen = V[k];
highLen =V[i];
j=k-1;
break;
}
}
}
i++;
}
【在 x*******6 的大作中提到】
: 后缀树理论建造需要n，再遍历所有internal node，每个internal node应该包含所有
: 经过这个node的string的信息，这样就能找到所有有common letter的string了。
|
g*******u
发帖数: 3948 | 27 这个现在比较直观
还有其他方法吗？
主要是 见完 最后找 product 还是个 N^2复杂度啊 这块能快吗？
大数据是不是就不行了 我觉得
因为这个题目肯定是面向大数据说的 小数据没意义 对吧
2)
【在 A*********c 的大作中提到】
: 嗯，用bit map表示单词，一个单词4 bytes，很高效，算相交的时候更快，就算O(n^2)
: 也可以接受。
: 感觉比anagram的想法好。
|
