Fast anagram solving
algorithm, anagram, big-o, ruby
Solution
Your big O should be `O(n*lg(n))` since the sort is the limiting function. If you try it with very big anagrams you will see a loss of performance higher than expected for an `O(n)` solution.
You can do an `O(n)` solution by comparing counts in two maps of characters => character counts.
There are definitely other solutions that work with approximately the same complexity but I don't think you can come up with anything faster than `O(n)`
Problem
Given two strings, I would like to determine whether or not they are anagrams of one another. Here is the solution that I came up with: ``` # output messages def anagram puts "Anagram!" exit end def not_anagram puts "Not an anagram!" exit end # main method if __FILE__ == $0 # read two strings from the command line first, second = gets.chomp, gets.chomp # special case 1 not_anagram if first.length != second.length # special case 2 anagram if first == second # general case # Two strings must have the exact same number of characters in the # correct case to be anagrams. # We can sort both strings and compare the results if first.chars.sort.join == second.chars.sort.join anagram else not_anagram end end ``` But I am thinking that there is probably a better one. I analyzed the efficiency of this solution, and came up with: - `chars`: splits a string into an array of characters `O(n)` - `sort`: sorts a string alphabetically, I don't know how sort is implemented in Ruby but I assumed `O(n log n)` since that is the generally best known sorting efficiency - `join`: builds a string from an array of characters `O(n)` - `==`: The string comparison itself will have to examine every character of the strings `2*O(n)` Given the above, I categorized the efficiency of the entire solution as `O(n log n)` since sorting had the highest efficiency. Is there a better way to do this that is more efficient than `O(n log n)`?