Prev: Analysis of detecting loops in a singly linked list.
Next: "Why Scripting Is Evil" -- comments?
From: mohangupta13 on 29 Apr 2010 10:03
Problem: Given two strings S1 & S2 , return the common elements in
both the strings ??

One way I thought is to take a b-bit vector ( assuming the range of
elements in the strings is 0-b) ...now in the first pass through the
string S1 set all those bit positions that have an element equal to
them . i.e set i'th bit if we an element with value i..
Now go through S2 and and AND the i'th bit if we have an element equal
to i. Now return the elements for which we have a bit set.

Now there are various problems with this 1) It assumes elements in the
range 0-b .2) It just returns one instance of the common element .i.e
if S1= AABCA and S2= AAABCBA o/p= ABC and not AAABC .

Can anyone please provide a better way to do this ( in possibly linear
time and as small space as possible)...??

Mohan
From: Ben Bacarisse on 29 Apr 2010 11:15
mohangupta13 <mohangupta13(a)gmail.com> writes:

> Problem: Given two strings S1 & S2 , return the common elements in
> both the strings ??
>
> One way I thought is to take a b-bit vector ( assuming the range of
> elements in the strings is 0-b) ...now in the first pass through the
> string S1 set all those bit positions that have an element equal to
> them . i.e set i'th bit if we an element with value i..
> Now go through S2 and and AND the i'th bit if we have an element equal
> to i. Now return the elements for which we have a bit set.
>
> Now there are various problems with this 1) It assumes elements in the
> range 0-b .2) It just returns one instance of the common element .i.e
> if S1= AABCA and S2= AAABCBA o/p= ABC and not AAABC .
>
> Can anyone please provide a better way to do this ( in possibly linear
> time and as small space as possible)...??

The small space makes it interesting. The hint below (I've put a page
break in because some people might consider this a spoiler) is probably
not space optimal.

Spoiler:

Hint: replace the vector of bits with a vector of integer counts.

--
Ben.
From: Pascal J. Bourguignon on 29 Apr 2010 13:55
mohangupta13 <mohangupta13(a)gmail.com> writes:

> Problem: Given two strings S1 & S2 , return the common elements in
> both the strings ??
>
> One way I thought is to take a b-bit vector ( assuming the range of
> elements in the strings is 0-b) ...now in the first pass through the
> string S1 set all those bit positions that have an element equal to
> them . i.e set i'th bit if we an element with value i..
> Now go through S2 and and AND the i'th bit if we have an element equal
> to i. Now return the elements for which we have a bit set.
>
> Now there are various problems with this 1) It assumes elements in the
> range 0-b .2) It just returns one instance of the common element .i.e
> if S1= AABCA and S2= AAABCBA o/p= ABC and not AAABC .
>
> Can anyone please provide a better way to do this ( in possibly linear
> time and as small space as possible)...??

The problem you have is that you don't specify what you want.

What does "the common elements in both the strings" mean?


Notice that "AAABC" is not a set of character, it's a string.

If you talk of elements in your specification, do you mean you want a
set of characters as result? Then your algorithm is ok.


If you want a substring or a list of substrings as result, you have to
specify it, and explain what you mean by "common [whatever] in both
strings"?



--
__Pascal Bourguignon__
From: Ben Bacarisse on 29 Apr 2010 17:49
pjb(a)informatimago.com (Pascal J. Bourguignon) writes:

> mohangupta13 <mohangupta13(a)gmail.com> writes:
>
>> Problem: Given two strings S1 & S2 , return the common elements in
>> both the strings ??
>>
>> One way I thought is to take a b-bit vector ( assuming the range of
>> elements in the strings is 0-b) ...now in the first pass through the
>> string S1 set all those bit positions that have an element equal to
>> them . i.e set i'th bit if we an element with value i..
>> Now go through S2 and and AND the i'th bit if we have an element equal
>> to i. Now return the elements for which we have a bit set.
>>
>> Now there are various problems with this 1) It assumes elements in the
>> range 0-b .2) It just returns one instance of the common element .i.e
>> if S1= AABCA and S2= AAABCBA o/p= ABC and not AAABC .
>>
>> Can anyone please provide a better way to do this ( in possibly linear
>> time and as small space as possible)...??
>
> The problem you have is that you don't specify what you want.
>
> What does "the common elements in both the strings" mean?
>
> Notice that "AAABC" is not a set of character, it's a string.
>
> If you talk of elements in your specification, do you mean you want a
> set of characters as result? Then your algorithm is ok.

From his example I concluded that he wants the intersection of the
multisets represented by the two strings. Though both the input and
results are strings, the significance is only in the number of
repetitions of each letter.

<snip>
--
Ben.
From: Daniel T. on 29 Apr 2010 18:26
mohangupta13 <mohangupta13(a)gmail.com> wrote:

> Problem: Given two strings S1 & S2 , return the common elements in
> both the strings ??
>
> One way I thought is to take a b-bit vector ( assuming the range of
> elements in the strings is 0-b) ...now in the first pass through the
> string S1 set all those bit positions that have an element equal to
> them . i.e set i'th bit if we an element with value i..
> Now go through S2 and and AND the i'th bit if we have an element equal
> to i. Now return the elements for which we have a bit set.
>
> Now there are various problems with this 1) It assumes elements in the
> range 0-b .2) It just returns one instance of the common element .i.e
> if S1= AABCA and S2= AAABCBA o/p= ABC and not AAABC .

Sort both strings and do a set intersection on them. Set intersection is
a pretty simple algorithm and depending on the language you are using,
it might even exist as a library primitive or included function.

What language are you using?
 |  Next  |  Last
Pages: 1 2 3
Prev: Analysis of detecting loops in a singly linked list.
Next: "Why Scripting Is Evil" -- comments?