Menu
How would you list words that are anagrams of each other?
I was asked this question when I applied for my current job.
orchestra can be rearranged into carthorse with all original letters used exactly once therefore the words are anagrams of each other.
845
Two words are anagrams of each other if they contain the same number of characters and the same characters. You should only need to sort the characters in lexicographic order, and determine if all the characters in one string are equal to and in the same order as all of the characters in the other string.
Approach: Create two arrays freqA[] and freqB[] where freqA[i] and freqB[i] will store the frequency of digit i in a and b respectively. Now traverse the frequency arrays and for any digit i if freqA[i] != freqB[i] then the numbers are not anagrams of each other else they are.
Put all the letters in alphabetical order in the string (sorting algorithm) and then compare the resulting string.
199
Good thing we all live in the C# reality of in-place sorting of short words on quad core machines with oozles of memory. :-)
However, if you happen to be memory constrained and can't touch the original data and you know that those words contain characters from the lower half of the ASCII table, you could go for a different algorithm that counts the occurrence of each letter in each word instead of sorting.
You could also opt for that algorithm if you want to do it in O(N) and don't care about the memory usage (a counter for each Unicode char can be quite expensive).
44
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
