Prompt: Given a list of strings, return groups of strings that are anagrams of each other.
Note: An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Input: strs = [""]
Output: [[""]]
Input: strs = ["a"]
Output: [["a"]]
Solution: A simple solution is to use a dictionary. We can have a key that is related to all anagrams within the same group and the value could be the list of words that are within the same group of anagrams.
A general key that is related to all anagrams within the same group is the sorted version of the anagram. For example:
- “eat” → “aet”
- “tea” → “aet”
First, we can set up a default dictionary with the values being a list. Then, we can loop through all words and store them in the dictionary’s value/list with the key being the sorted version of the word.
Finally, the answer would be the list of all the values in the dictionary. The time complexity would be linear since we looped through all words and each word was sorted with python’s sort algorithm, which is a variation of merge sort with a time complexity of O(n log n). Hence, the total time complexity is O(n2 log n).