Given a set of random strings, write a function that returns a set that groups all the anagrams together in objective-c

Question

I would like to get feedback on the solution and a question regarding Big O.
I am first converting each character in the string into the array and that would be O(n) then i am sorting the array O(n log n) and then I join back the array. Not sure if that is O(n). After i get the sorted string I would retrieve the NSArray from NSDictionary if it is there and either add the word to the array or create a new array and then set it back into the NSDictionary. I would those operations are O(1). The total runtime complexity is O(N log N) because of sort. Is that the correct breakdown.

void printAllAnagrams(NSArray *words)
{
    NSMutableDictionary *anagramsDictionary = [[NSMutableDictionary alloc]init];
    NSMutableArray *wordArray = [[NSMutableArray alloc]init];

    for(NSString *word in words){

        //Loop through each word
        for(int i = 0;i < [word length]; i++){
            //create a character array
            [wordArray addObject:[NSString stringWithFormat:@"%c",[word characterAtIndex:i]]];
        }

        //sort character array
        [wordArray sortUsingSelector:@selector(localizedCompare:)];
        //convert character array back to string to use it as a key for in the dictionary
        NSString *sortedString = [wordArray componentsJoinedByString:@""];
        NSMutableArray *anagramStrings =[[anagramsDictionary objectForKey:sortedString] mutableCopy];

        if(anagramStrings){
            //if anagram(s) of the word is already in the dictionary then add this word to the array
            //and store it back into the dictionary
            [anagramStrings addObject:word];
            [anagramsDictionary setObject:anagramStrings forKey:sortedString];
        }else{
            //create an array with current word and store it in the dictionary
            //using the sorted characters string as the key
            [anagramsDictionary setObject:@[word] forKey:sortedString];
        }
        [wordArray removeAllObjects];
    }
    NSLog(@"%@",anagramsDictionary);
}

Answer 1

This would be a better way to do the final storage into the dictionary. Attempt to retrieve an existing list. If it does not exist, create it and add it to the dictionary. You can then unconditionally add the current word to the array.

NSString *sortedString = [wordArray componentsJoinedByString:@""];

// Attempt to retrieve existing list
NSMutableArray * anagramStrings = [anagramsDictionary objectForKey:sortedString];
if( !anagramStrings ){
    // If it does not exist, create it and put it into the dictionary
    anagramStrings = [NSMutableArray array];
    [anagramDictionary setObject:anagramStrings forKey:sortedString];
}

// Add to the list
[anagramStrings addObject:word];

[wordArray removeAllObjects];

This avoids doing a copy every time, which in your original code is unnecessary in all cases but one.

Also worth noting is the last line here:

if(anagramStrings){
    //if anagram(s) of the word is already in the dictionary then add this word to the array
    //and store it back into the dictionary
    [anagramStrings addObject:word];
    [anagramsDictionary setObject:anagramStrings forKey:sortedString];
}

There is no need to put the mutable array back into the dictionary after getting a pointer to it, as you're doing. The array is not removed from the dictionary; your anagramStrings points to that exact same array.

Answer 2

Not quite right, though you're headed in the right direction since the complexity of a procedure can't be lower than the most complex part of it. If you have an operation that's O(n), and another one that's O(n log n), their sequential combination's upper bound is O(n log n).

But that's not quite what you have. First, your sort is being run once for every value in the input. That means it's not O(n) + O(n log n), but O(n) × O(n log n), or O(n² log n). Perhaps more importantly, though, it isn't operating on the data that we're counting with n. The input to the sort is not the same as the input to the outer procedure: you're decomposing each piece of the outer data to produce a new set of data. We can call this new set's size m, and then you have O(m log m) for the sort. The value of m will vary, but its expected average value is probably much lower than n. Still, the complexity for this loop is O(n × m log m) assuming that m is not completely negligible.

There is also one other internal loop that may need to be considered, unfortunately. The dictionary accesses are not necessarily constant time. The expected time for a lookup is given in CFDictionary.h as O(1), but the worst time of O(n) is possible. Likewise, insertion should be constant but may be as bad as O(n²). I think it's worth noting that this n -- the size of the dictionary -- is not precisely the same as that of the input array; in fact it's guaranteed to be strictly smaller until the very end of the procedure. Its average size is n/2, however, and the 2 being a constant factor, it's removed from consideration, leaving us with just n.

Thus, the worst possible running time your procedure could incur would be O(n³ × m log m), but it's much more likely to be simply O(n × m log m) where m is the expected length of a word in the array.