Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Finding common characters of two strings in O(n)

 
Arka Sharma
Ranch Hand
Posts: 103
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 287
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Campbell Ritchie
Sheriff
Pie
Posts: 47293
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 9486
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Campbell Ritchie
Sheriff
Pie
Posts: 47293
52
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good idea; you would get t-h-r-e from three and e-t-h-r from ether.
 
Don't get me started about those stupid light bulbs.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic