aspose file tools*
The moose likes Java in General and the fly likes Finding common characters of two strings in O(n) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Finding common characters of two strings in O(n)" Watch "Finding common characters of two strings in O(n)" New topic
Author

Finding common characters of two strings in O(n)

Arka Sharma
Ranch Hand

Joined: Jun 15, 2011
Posts: 103
Hi,
The following code I have written to find common characters between two strings.Can we do it in a better way but within linear time?


Regards,
Arka
Harsha Smith
Ranch Hand

Joined: Jul 18, 2011
Posts: 287
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39396
    
  28
It all depends what you mean by common characters. Do “CAMPBELL” and “RITCHIE” have C and E as common characters because C and E both appear? Or do they have no common characters because the first two characters are different, the second two different, etc. In the latter case “three” and “ether” would have one e in common, as the 4th character, which can be found as pairs in linear time by iterating the String. If you use the set solution above, you will get 4 duplicates: ehrt, because those two words are anagrams of each other.

But that Set thing is a good solution, which will also run in linear time.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Just a small point: if Harsha's solution was changed to use LinkedHashSet's, it's likely that the original character order would be retained in the resulting Set, admittedly at a small (but linear) cost in speed.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39396
    
  28
Good idea; you would get t-h-r-e from three and e-t-h-r from ether.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Finding common characters of two strings in O(n)