C, 32mS solution in one pass


  • 0
    M

    One method to evaluate anagrams would be to simply sort the characters, and then do a comparison. Or instead of sorting we can also use a character map, something like below. Anagrams would essentially share the same map.

    int map[26] = {0};
    
     /* Loop through the string and increment the character count */
    for (i = 0; str[i] != 0; ++i)    
            map[str[i] - 97] += 1;
    
    

    The above operation basically transforms anagrams like "eat", "tea" into the same string "aet". These transformed strings can be now be pushed into a trie. So now our basic problem of searching for anagrams can be resolved with linear time complexity O(n), where n is the length of the string. But the obvious downside of using a tree is that the memory usage grows exponentially.

    Accepted C code has some additional optiomizations also, it is uploaded here


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.