String containing algorithm
 

Hi all,
Can anyone help me with a small problem I'm having. I need to write a method
which takes two Strings of any lengths and returns any letters which are
common between the two. The Strings will be something like ABECA and they
could be of any length.

For example:
ABECA and ECDRE would return EC, I dont mind about the order which they come
in because I am processing them further anyway.

I just cant get any algorithms to work on it, not even brute force.
Any help is appreciated, thanks in advance.
JS

Re: String containing algorithm
 

"JS" <james.sarjeant90@ntlworld.com> wrote in
news:TSIhf.4040$GC1.282@newsfe6-gui.ntli.net:

> Hi all,
> Can anyone help me with a small problem I'm having. I need to write a
> method which takes two Strings of any lengths and returns any letters
> which are common between the two. The Strings will be something like
> ABECA and they could be of any length.
>
> For example:
> ABECA and ECDRE would return EC, I dont mind about the order which
> they come in because I am processing them further anyway.
>
> I just cant get any algorithms to work on it, not even brute force.
> Any help is appreciated, thanks in advance.
> JS
>
>
>

This sounds suspiciously like a homework assignment.

Here's a possible algorithm (no code, I'm sure you can handle that
yourself)

prerequisites: Strings A and B of arbitrary length; empty string (or
stringbuffer) C.

1. take the first character in string A, and compare it to every
character in B
1a. alternative to 1: take the first character in string A, turn it into
a CharSequence, and use String method contains()
2. if you have a match, add it to a C
3. take the next character in A, and we're back at 1.

If you want a case-insensitive algorithm just add toLowerCase or
toUpperCase.

If you want to weed out duplicates, check if the current character is
already contained in C.

--
Beware the False Authority Syndrome

Re: String containing algorithm
 

On Fri, 25 Nov 2005 18:38:43 GMT, "JS" <james.sarjeant90@ntlworld.com>
wrote, quoted or indirectly quoted someone who said :

>For example:
>ABECA and ECDRE would return EC, I dont mind about the order which they come
>in because I am processing them further anyway.

I would do it with two java.util.BitSets
each 64K bits long (possibly shorter if you can guarantee a narrower
char range.). Go through String a turning on bits corresponding to
chars in bita. (index bit by char number). Then repeat with b and
bitb.

Then compute the logical AND of bita and bitb.
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Re: String containing algorithm
 

On Fri, 25 Nov 2005 18:38:43 GMT, "JS" <james.sarjeant90@ntlworld.com>
wrote, quoted or indirectly quoted someone who said :

>For example:
>ABECA and ECDRE would return EC, I dont mind about the order which they come
>in because I am processing them further anyway.

another approach is to create a HashSet of the chars in string a. Then
create another HashSet for String b. Then enumerate HashSet b and
remove els that don't exist in set a.

Another approach to is use a nested loop

pseudocode:

for each char in string a
for each char in string b

if achar == bchar add to HashSet if not already there.
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Re: String containing algorithm
 

JS wrote:
> Hi all,
> Can anyone help me with a small problem I'm having. I need to write a method
> which takes two Strings of any lengths and returns any letters which are
> common between the two. The Strings will be something like ABECA and they
> could be of any length.
>
> For example:
> ABECA and ECDRE would return EC, I dont mind about the order which they come
> in because I am processing them further anyway.

Please clarify. Your example fits your text, but it also matches a
"longest common substring" search. The answers you've received so far
appear to address both of these.

For instance, what happens if you use "ABCDEF" and "FEDCBA"? If it's
all the letters in common in both strings, you'll get "ABCDEF" in some
permutation. If it's a longest common substring, you'll get one of the
letters.

If you're truly just searching for all letters in common between the two
strings, you might want to use a HashSet<Character> for each string, add
each character in each string to its respective HashSet, and obtain
the set of common characters by intersecting the sets.

Re: String containing algorithm
 

Roedy Green wrote:
> On Fri, 25 Nov 2005 18:38:43 GMT, "JS" <james.sarjeant90@ntlworld.com>
> wrote, quoted or indirectly quoted someone who said :
>
>>For example:
>>ABECA and ECDRE would return EC, I dont mind about the order which they come
>>in because I am processing them further anyway.
>
> another approach is to create a HashSet of the chars in string a. Then
> create another HashSet for String b. Then enumerate HashSet b and
> remove els that don't exist in set a.

Set.retainAll already does that last bit.

> Another approach to is use a nested loop
>
> pseudocode:
>
> for each char in string a
> for each char in string b
> if achar == bchar add to HashSet if not already there.

That's unnecessarily O(n^2) - not horrible for a quick-and-dirty, but to
be avoided in production and homework assignments. Sorting them and
then linearly merging them would be O(n log n), and the HashSet approach
is O(n) when the hash table is large enough and the hash function is
well-tuned to the data.

Re: String containing algorithm
 

Roedy Green wrote:
> On Fri, 25 Nov 2005 18:38:43 GMT, "JS" <james.sarjeant90@ntlworld.com>
> wrote, quoted or indirectly quoted someone who said :
>
>>For example:
>>ABECA and ECDRE would return EC, I dont mind about the order which they come
>>in because I am processing them further anyway.
>
> I would do it with two java.util.BitSets
> each 64K bits long (possibly shorter if you can guarantee a narrower
> char range.). Go through String a turning on bits corresponding to
> chars in bita. (index bit by char number). Then repeat with b and
> bitb.

A sparse set implementation would be better; if you have string lengths
far below 64K, it's not going to use very much of that space.

Plus, while Java represents characters internally in UTF-16, there are
far more than 2^16 code points possible.

Re: String containing algorithm
 

On Fri, 25 Nov 2005 16:16:12 -0600, Alan Krueger
<wgzkid502@sneakemail.com> wrote, quoted or indirectly quoted someone
who said :

>Plus, while Java represents characters internally in UTF-16, there are
>far more than 2^16 code points possible.

char is 16 bits so there can't possibly be more than 2^16 = 64K
combinations. With a java.util.BitSet you can track presence with 8K
bytes worth of bits (stored as longs in a BitSet).

most of the time you have an upper bound on your unicode chars
considerably lower than 64K.

The advantage of BitSet is the speed of direct addressing. Any sparce
scheme will have a lot of lookup overhead.
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Re: String containing algorithm
 

Roedy Green wrote:
> On Fri, 25 Nov 2005 16:16:12 -0600, Alan Krueger
> <wgzkid502@sneakemail.com> wrote, quoted or indirectly quoted someone
> who said :
>
>>Plus, while Java represents characters internally in UTF-16, there are
>>far more than 2^16 code points possible.
>
> char is 16 bits so there can't possibly be more than 2^16 = 64K
> combinations.

There cannot be more than 2^16 char values, but there are far more than
2^16 Unicode code points, depending on your version of Unicode.

http://java.sun.com/developer/techni...Supplementary/

"Supplementary characters are characters in the Unicode
standard whose code points are above U+FFFF, and which
therefore cannot be described as single 16-bit entities
such as the char data type in the Java programming
language. [...]

"These are now interpreted as UTF-16 sequences, and the
implementations of these APIs is changed to correctly
handle supplementary characters. The enhancements are
part of version 5.0 of the Java 2 Platform, Standard
Edition (J2SE) [...]

"The Unicode standard therefore has been extended to allow
up to 1,112,064 characters."

Because it's UTF-16, these characters are serialized into 16-bit
character sequences, which means that not every character represents a
single Unicode code point, sometimes multiple characters are used.

> most of the time you have an upper bound on your unicode chars
> considerably lower than 64K.
>
> The advantage of BitSet is the speed of direct addressing. Any sparce
> scheme will have a lot of lookup overhead.

No, a properly-sized HashSet will have CONSTANT TIME lookup, just like a
lookup table.

Re: String containing algorithm
 

Thanks everyone for your help. The easiest one sounds like zeros idea which
should work a treat. I'm not worried about the time of the algorithm because
it isnt for submission or publication anywhere, and for those of you still
left wondering, sorry about my explaination, i meant any letters in any
order regardless of where they are.
Thanks again
JS
"Alan Krueger" <wgzkid502@sneakemail.com> wrote in message
news:nLLhf.764$7p7.621@fe06.lga...
> JS wrote:
> > Hi all,
> > Can anyone help me with a small problem I'm having. I need to write a
method
> > which takes two Strings of any lengths and returns any letters which are
> > common between the two. The Strings will be something like ABECA and
they
> > could be of any length.
> >
> > For example:
> > ABECA and ECDRE would return EC, I dont mind about the order which they
come
> > in because I am processing them further anyway.
>
> Please clarify. Your example fits your text, but it also matches a
> "longest common substring" search. The answers you've received so far
> appear to address both of these.
>
> For instance, what happens if you use "ABCDEF" and "FEDCBA"? If it's
> all the letters in common in both strings, you'll get "ABCDEF" in some
> permutation. If it's a longest common substring, you'll get one of the
> letters.
>
> If you're truly just searching for all letters in common between the two
> strings, you might want to use a HashSet<Character> for each string, add
> each character in each string to its respective HashSet, and obtain
> the set of common characters by intersecting the sets.