s*****i
发帖数: 32 | 1 Given a list of words, find two strings S & T such that:
a. S & T have no common character
b. S.length() * T.length() is maximized
Follow up: how to optimize and speed up your algorithm
前面有讨论用一个int来决定S和T是否有common character。但S.length() * T.length
() 还需要找出n^2个组合，这个有办法降低吗？ |
s******t
发帖数: 229 | |
x****g
发帖数: 1512 | 3 我很想知道你怎么dp? 请指教，谢谢！
【在 s******t 的大作中提到】
: dp吧
|
d******b
发帖数: 73 | 4 这个题 不用dp。
直接用bitset就搞定了。
每一个 字符串 对应一个 bitset，或者 32位的整数，如果只是 字母的话。
如果有 这个字母，相应的位 就 mark 1，否则mark 0。
然后 以第一个为基准，扫描到 逻辑和 不为零的 全部删掉。
一直这样做下去。 直到找到逻辑和 为零的。
平均复杂度，应该在 nlog(n) 。
至于第二个，应该是在第一个的基础上，找出两个最大的。
这个不难了。 |
x****g
发帖数: 1512 | 5 “平均复杂度，应该在 nlog(n) 。”
你是怎么想当然算的？
【在 d******b 的大作中提到】
: 这个题 不用dp。
: 直接用bitset就搞定了。
: 每一个 字符串 对应一个 bitset，或者 32位的整数，如果只是 字母的话。
: 如果有 这个字母，相应的位 就 mark 1，否则mark 0。
: 然后 以第一个为基准，扫描到 逻辑和 不为零的 全部删掉。
: 一直这样做下去。 直到找到逻辑和 为零的。
: 平均复杂度，应该在 nlog(n) 。
: 至于第二个，应该是在第一个的基础上，找出两个最大的。
: 这个不难了。
|
s******t
发帖数: 229 | 6 compare有没有common char当然是o（n）了，这步简单啊，后面求最大长度只能穷举吧
？不然sort之后再穷举？有什么其他办法优化？ |
f******s
发帖数: 25 | 7 可以建一个inverted index
然后扫面每个string, 并且排除有common character的string
最后如果有其他string生下来了，就找到结果了。
这样建立inverted index时间复杂度是O(n)
扫描时间复杂度是O(n)*O(len of string) |
s******t
发帖数: 229 | 8 剩余string再sort出结果？
【在 f******s 的大作中提到】
: 可以建一个inverted index
: 然后扫面每个string, 并且排除有common character的string
: 最后如果有其他string生下来了，就找到结果了。
: 这样建立inverted index时间复杂度是O(n)
: 扫描时间复杂度是O(n)*O(len of string)
|
f******s
发帖数: 25 | 9 不用sort, 剩余的string都和target string没有common characters.
所以任意一个和target string一起就是一个solution
【在 s******t 的大作中提到】
: 剩余string再sort出结果？
|
s******t
发帖数: 229 | 10 没太明白，不是得求最大s1.len * s2.len 吗?
按照你的方法可以得到很多符合条件的string pair,但是不sort怎么求最大呢？
我觉得扫描过程中没法存最大吧，因为要不断的要删掉不符合条件的stringpair啊
【在 f******s 的大作中提到】
: 不用sort, 剩余的string都和target string没有common characters.
: 所以任意一个和target string一起就是一个solution
|
|
|
f******s
发帖数: 25 | 11 (⊙o⊙)哦， 没有注意maximize len*len的条件。
那就把所有的string都在inverted index中扫一遍，然后选一个符合条件的最长串和他
匹配。
需要事先按照串的长度sort一下。
找符合条件的最长串可以用一个bitset，unset所有不符合条件的串， 然后用位操作找
出least significant 1的位置就是最长的串
【在 s******t 的大作中提到】
: 没太明白，不是得求最大s1.len * s2.len 吗?
: 按照你的方法可以得到很多符合条件的string pair,但是不sort怎么求最大呢？
: 我觉得扫描过程中没法存最大吧，因为要不断的要删掉不符合条件的stringpair啊
|
d******b
发帖数: 73 | 12 首先，有上界 O(n^2)
其次，有下界O(n)
还有再想想，每次扫描 都会 有一部分的bitset被删掉。
如果一个都没有被删那就是 答案。
每次扫描都是在上次扫描被删的基础上，
所以我说 应该在 O(nlogn)，当然你要说想当然也行。
【在 x****g 的大作中提到】
: “平均复杂度，应该在 nlog(n) 。”
: 你是怎么想当然算的？
|
x****g
发帖数: 1512 | 13 我就是想弄明白你怎么想的，呵呵。
怎么能删掉呢？
当前A,你扫描把和A相交的都删掉？这样有遗漏啊.....
你下次扫B,但和A相交的可能和B不相交已经被你删掉了？
【在 d******b 的大作中提到】
: 首先，有上界 O(n^2)
: 其次，有下界O(n)
: 还有再想想，每次扫描 都会 有一部分的bitset被删掉。
: 如果一个都没有被删那就是 答案。
: 每次扫描都是在上次扫描被删的基础上，
: 所以我说 应该在 O(nlogn)，当然你要说想当然也行。
|
s******t
发帖数: 229 | 14 不错，我还想用matrix，费空间，bitset好
【在 f******s 的大作中提到】
: (⊙o⊙)哦， 没有注意maximize len*len的条件。
: 那就把所有的string都在inverted index中扫一遍，然后选一个符合条件的最长串和他
: 匹配。
: 需要事先按照串的长度sort一下。
: 找符合条件的最长串可以用一个bitset，unset所有不符合条件的串， 然后用位操作找
: 出least significant 1的位置就是最长的串
|
d******b
发帖数: 73 | 15 你说的对，拍脑袋想出来的果然有问题。
【在 x****g 的大作中提到】
: 我就是想弄明白你怎么想的，呵呵。
: 怎么能删掉呢？
: 当前A,你扫描把和A相交的都删掉？这样有遗漏啊.....
: 你下次扫B,但和A相交的可能和B不相交已经被你删掉了？
|
s******t
发帖数: 229 | 16 dp=穷举
【在 x****g 的大作中提到】
: 我很想知道你怎么dp? 请指教，谢谢！
|
g*****g
发帖数: 212 | 17 不确定是否有 nLog(n)的解，不过 n^2的解法是可以调优的。
首先先把数组sort了，按长度降序
string s[];//
int signature[];//
int length[];// length of each string
int n; // length of s
int max = 0;
for(int i=0; i
{
for(int j=i+1; j
{
if (length[i] * length[j] <= max)
{
break; // optimize 1, early stop
}
if (signature[i] & signature[j] == 0)
{
max = max(length[i] * length[j], max);
break;// optimize 2, no need to test rest
}
}
}
length
【在 s*****i 的大作中提到】
: Given a list of words, find two strings S & T such that:
: a. S & T have no common character
: b. S.length() * T.length() is maximized
: Follow up: how to optimize and speed up your algorithm
: 前面有讨论用一个int来决定S和T是否有common character。但S.length() * T.length
: () 还需要找出n^2个组合，这个有办法降低吗？
|
b*********s
发帖数: 115 | 18 可以做到 O( l*n + a*2^a), 其中n是单次个数，a是字符范围个数（所有小写字母的话
a就是26），l 是 单词长度
下面Quora这个链接说的是求最大S.length() + T.length()的，改成S.length() * T.
length()算法是一样的，就最后一步把求最大和改成最大积而已
http://www.quora.com/Algorithms/Given-a-dictionary-of-words-how |
s*****i
发帖数: 32 | 19 没有quora帐号，楼主可否直接copy色鲁迅过来。
谢谢！
【在 b*********s 的大作中提到】
: 可以做到 O( l*n + a*2^a), 其中n是单次个数，a是字符范围个数（所有小写字母的话
: a就是26），l 是 单词长度
: 下面Quora这个链接说的是求最大S.length() + T.length()的，改成S.length() * T.
: length()算法是一样的，就最后一步把求最大和改成最大积而已
: http://www.quora.com/Algorithms/Given-a-dictionary-of-words-how
|
D**********d
发帖数: 849 | 20 2^{26} = 64M
计算 64M 个组合的 max_length
扫描一遍，binary tree 分支统计 branch 最长长度，
维持 current maximum value |
