What is the fast way to find all anagrams inside an array in objective c?

Question

I have an array that contains multiple words in there. The problem is asking me to find all the anagrams in there and pick out which one has the most anagrams. This is what I have so far:

• Create a duplicate array of the old array.
• Create an index array for the old array, to keep track of where every word is located. This index value won't be changed throughout the program
• For the new array, I will be sort each individual word in the array.

For example: Before sorting, array has: [cat dog tac god act] then after that, it will have [act dgo act dgo act]

• Sort the word in the array, then the array now will have: [act act act dgo dgo]. Now we can see that all anagrams has come together, but the order has changed in the the new array.
• Use in the index array to keep track of the order of the words in the old array.

This approach seems to be good, but it depends on the number of the words that I have in the original array. If my original array is big enough, it could slow down the program due to copying process. Moreover, there is no way that I could keep track how many anagrams for each word. What could be the best approach to this kind of problem, consider that the array is big and the program has to find all the anagrams in a fast way ? Any help would be greatly appreciated. Thank you.

Answer 1

I think I would do something like this...

1. Create an NSCountedSet called anagramCounts. The objects in here will be a sorted array of letters.
2. Iterate your word array.
3. Turn each word into an array of letters.
4. Sort this array alphabetically.
5. Add the sorted array to the anagramCounts set.

After doing this the anagramCounts set will have all of the possible anagrams only once each and each will be stored next to a count of how many there are.

You can then get the object enumerator from this set and find the one with the highest count...

Or even... Add this to the previous list.

On the beginning

1. Create an NSInteger called highestAnagramCount and set it to 0.
2. Create an NSArray called mostCommonAnagram and leave it as nil.

...

On the end

1. Get [anagramCounts countForObject:sortedArray]; and if it is higher than highestAnagramCount then save this new value out and save the array.
2. At the end highestAnagramCount will tell you how many anagrams there are and mostCommonAnagram will contain the sorted array of letters.