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 EJB 3 in Action this week in the EJB and other Java EE Technologies 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: 36482
    
  16
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: 7052
    
  16

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?
Artlicles by Winston can be found here
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36482
    
  16
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)
 
Similar Threads
Merge Sort
June Newsletter Puzzle
Sorting two dimensional array
Character Array Question in Core Java
adding two arrays