s*******n
发帖数: 344 | 1 面试题目：
有２个字符串，消除第一个字符串中第二个字符串包含的所有字母。
例如：
string1: helloworld
string2: abcdef
output: hlloworld
面试的时候我说了很笨的办法。因为不许allocate新的空间。
大家帮我说说最好的解法应该是什么？谢谢了 |
r*******y
发帖数: 1081 | 2 sort string2 first? then binary search ?
【在 s*******n 的大作中提到】
: 面试题目：
: 有２个字符串，消除第一个字符串中第二个字符串包含的所有字母。
: 例如：
: string1: helloworld
: string2: abcdef
: output: hlloworld
: 面试的时候我说了很笨的办法。因为不许allocate新的空间。
: 大家帮我说说最好的解法应该是什么？谢谢了
|
g***s
发帖数: 3811 | 3 after deleting 26 chars, use these space as a simple hashmap.
【在 r*******y 的大作中提到】
: sort string2 first? then binary search ?
|
r*******y
发帖数: 1081 | 4 smart idea
【在 g***s 的大作中提到】
: after deleting 26 chars, use these space as a simple hashmap.
|
c******t
发帖数: 391 | 5 So how do we efficiently delete the target letters without additional
storage? |
h*********n
发帖数: 11319 | 6 果然要always think of hash first...
【在 g***s 的大作中提到】
: after deleting 26 chars, use these space as a simple hashmap.
|
w**s
发帖数: 141 | 7 why deleting 26 chars??? Not really understanding...
【在 g***s 的大作中提到】
: after deleting 26 chars, use these space as a simple hashmap.
|
g**********y
发帖数: 14569 | 8 delete 26个char是什么意思？同不明白。 |
d*******l
发帖数: 338 | 9 我感觉这个问题可以用grass之前在另一个thread里提到的那个方法，就是
while(s[i] != s[s[i]-'a']) swap(s[i], s[s[i]]);
这里写的比较粗略，没考虑大写字母。相当于把每个字母换到对应的位置上，然后可以
作为hashmap来用。不过这需要string2长度至少是26，而且会破坏string2，不知道是
否符合要求。然后扫一遍string1就可以了。 |
i**********e
发帖数: 1145 | 10 我想就是利用两个前后指针扫描，然后首先可以用简单的 linear search 来寻找重复
的。直到后指针与前指针的距离为 26，那也意为着有 26 个连续的空位。这时候就把
后指针指向和之后的所有元素往前移 26位，然后利用最后的 26 空位来当 hash。
也就是 grass 所说的是从 string1 里删除了二十六个重复的字母之后，利用剩下的二十六
个空位来当作hash来用。
这是考虑到 string1 的长度非常长。但是有一个最坏情况就是万一很久都没碰上重复的字母怎么办？抑或是 string1 产生重复的个别字母不超过 string2 的长度？那这基本上就跟 worst case 一样，26*n 的比较次数，那还不如把 string2 排好序，然后做 binary search。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*******n 的大作中提到】
: 面试题目：
: 有２个字符串，消除第一个字符串中第二个字符串包含的所有字母。
: 例如：
: string1: helloworld
: string2: abcdef
: output: hlloworld
: 面试的时候我说了很笨的办法。因为不许allocate新的空间。
: 大家帮我说说最好的解法应该是什么？谢谢了
|
|
|
M*****e
发帖数: 568 | 11
Depends the size of the Alphabet, and the length of the second string.
If the alphabet is small (e.g., English char), create a hash table for that
- O(size of alphabet * len_string1). If the second string is small, (e.g.,
1 char), brute force search on the first string - O(len_string1 * len_
string2). If both are large, sort the second string, and go over the first
string while binary look up each char in the sorted second string - O(lg(len
_string2) * (len_string2 + len_string1)).
【在 s*******n 的大作中提到】
: 面试题目：
: 有２个字符串，消除第一个字符串中第二个字符串包含的所有字母。
: 例如：
: string1: helloworld
: string2: abcdef
: output: hlloworld
: 面试的时候我说了很笨的办法。因为不许allocate新的空间。
: 大家帮我说说最好的解法应该是什么？谢谢了
|
g***s
发帖数: 3811 | 12 I replied the 2 lou(who mentioned to use sort+binary search to delete
first) and i agreed. (if string2 is very small, scan could be faster
because of binary search overhead)
After enough chars(26 or 52 or 256) are deleted, we can compact it and
use the deleted space.
All we assume is that string1 is very large.
二十六
复的字母怎
么办？抑或是 string1 产生重复的个别字母不超过 string2 的长度？那这基本上就跟
worst
case 一样，26*n 的比较次数，那还不如把 string2 排好序，然后做 binary search。
【在 i**********e 的大作中提到】
: 我想就是利用两个前后指针扫描，然后首先可以用简单的 linear search 来寻找重复
: 的。直到后指针与前指针的距离为 26，那也意为着有 26 个连续的空位。这时候就把
: 后指针指向和之后的所有元素往前移 26位，然后利用最后的 26 空位来当 hash。
: 也就是 grass 所说的是从 string1 里删除了二十六个重复的字母之后，利用剩下的二十六
: 个空位来当作hash来用。
: 这是考虑到 string1 的长度非常长。但是有一个最坏情况就是万一很久都没碰上重复的字母怎么办？抑或是 string1 产生重复的个别字母不超过 string2 的长度？那这基本上就跟 worst case 一样，26*n 的比较次数，那还不如把 string2 排好序，然后做 binary search。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
s*****y
发帖数: 897 | 13 一个字符8bit，4个字符就有32个bit可以做bitmap hash 26个字符了，这样子可以吗
唯一的就是当第一个字符如果它的bitmap影射到第2个字符，那么在读第2个字符前就会
破坏了第2个字符。 |
f****4
发帖数: 1359 | 14 还有个办法是破坏string2，只要string2有>=4个char，就有32bits，每个bit代表一个
字母；遍历string2剩下字符然后设置string2前26bits。
用这26bits做hashmap，遍历string1
这样就避免了string1 move char
如果string2 size<4; 直接查找即可 |
m********l
发帖数: 4394 | 15 不能用XOR?
helloworld
^aaaaaaaaaa
delete any zero.
^aaaaaaaaaa
...
helloworld
^eeeeeeeeee
delete any zero.
^eeeeeeeeee
【在 s*******n 的大作中提到】
: 面试题目：
: 有２个字符串，消除第一个字符串中第二个字符串包含的所有字母。
: 例如：
: string1: helloworld
: string2: abcdef
: output: hlloworld
: 面试的时候我说了很笨的办法。因为不许allocate新的空间。
: 大家帮我说说最好的解法应该是什么？谢谢了
|
d*******l
发帖数: 338 | 16 感觉有点南辕北辙。。相同的字母xor了确实会变成0，但不同的字母xor结果不就乱了
？除非不同的字母的对应的是全0，但这样意义很小，对效率好像也没什么帮助
【在 m********l 的大作中提到】
: 不能用XOR?
: helloworld
: ^aaaaaaaaaa
: delete any zero.
: ^aaaaaaaaaa
: ...
: helloworld
: ^eeeeeeeeee
: delete any zero.
: ^eeeeeeeeee
|
m********l
发帖数: 4394 | 17
XOR两次
没仔细读.. 不准用新空间
不过他问题也没说好
output跟string1是同个空间吗?
helloworld 是要变成 hlloworl
多了个d
【在 d*******l 的大作中提到】
: 感觉有点南辕北辙。。相同的字母xor了确实会变成0，但不同的字母xor结果不就乱了
: ？除非不同的字母的对应的是全0，但这样意义很小，对效率好像也没什么帮助
|
m********l
发帖数: 4394 | 18 昨晚在外面想了个方法
用bit encoding.
比如说
0001 = a
0010 = b
0100 = c
1000 = d
0001 0000=e
0010 0000=f
...
用26-bit. (4 bytes)
然后
string2 = (1 <
int i=0;
while(string1[i])
{
if ((1 << (string1[i]-'a')) & string2 == 0) cout << string[i];
i++;
}
【在 s*******n 的大作中提到】
: 面试题目：
: 有２个字符串，消除第一个字符串中第二个字符串包含的所有字母。
: 例如：
: string1: helloworld
: string2: abcdef
: output: hlloworld
: 面试的时候我说了很笨的办法。因为不许allocate新的空间。
: 大家帮我说说最好的解法应该是什么？谢谢了
|
f****4
发帖数: 1359 | 19 恩，用string2 做mapping比较方便
【在 m********l 的大作中提到】
: 昨晚在外面想了个方法
: 用bit encoding.
: 比如说
: 0001 = a
: 0010 = b
: 0100 = c
: 1000 = d
: 0001 0000=e
: 0010 0000=f
: ...
|
