Detect anagram in array

Question

Given an array of strings, write a function to detect and return all pairs of strings that are anagrams of each other. An anagram is defined as a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once. The output should be a list of tuples, where each tuple contains two anagram strings from the input array.

Codemia · Accepted Answer

To detect anagrams in an array of strings, we can leverage a hash map (dictionary) to group words that are anagrams of each other. The specific pattern we will use here is sorting each word as the key in the dictionary. When two words are anagrams, their sorted character sequences will match. For example, the strings 'listen' and 'silent' both become 'eilnst' when sorted. This approach efficiently groups anagrams together and allows us to easily retrieve pairs.

1. Initialize an empty dictionary to store sorted character sequences as keys and lists of words as values.  
2. Iterate through each string in the input array:  
   - Sort the string to create a key.  
   - If the key is already in the dictionary, append the string to the list for that key. If not, create a new entry in the dictionary with the sorted string as the key.  
3. After processing all strings, iterate through the values in the dictionary. For each list with more than one word, generate all unique pairs of anagram strings and store them in a result list.  
4. Return the result list of tuples containing anagram pairs.  
Example: Given input ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'], the dictionary would look like:  
{ 'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat'] }. The output would be [('eat', 'tea'), ('eat', 'ate'), ('tea', 'ate'), ('tan', 'nat')].

```python
from collections import defaultdict

def detect_anagrams(words):
    anagram_map = defaultdict(list)
    
    for word in words:
        sorted_word = ''.join(sorted(word))  # Sort the word to get the key
        anagram_map[sorted_word].append(word)  # Append the word to the corresponding list
    
    result = []
    for word_list in anagram_map.values():
        if len(word_list) > 1:  # Consider only lists with more than one word
            for i in range(len(word_list)):
                for j in range(i + 1, len(word_list)):
                    result.append((word_list[i], word_list[j]))  # Create pairs
    
    return result
```

The time complexity of this algorithm is O(n * k log k), where n is the number of strings and k is the maximum length of a string. Sorting each string takes O(k log k), and we do this for n strings. The space complexity is O(n) for storing the words in the dictionary. In the worst case, all words are anagrams and stored together, resulting in a list of size n.

1. **Empty Input**: If the input array is empty, the output should also be an empty list.  
   - Input: []  
   - Output: []  
2. **Single Element**: If there is only one string in the array, no pairs can be formed.  
   - Input: ['hello']  
   - Output: []  
3. **All Unique Words**: If all words are unique with no anagrams, the output should be empty.  
   - Input: ['abc', 'def', 'ghi']  
   - Output: []  
4. **Multiple Anagrams**: Ensure that pairs are generated correctly when there are multiple anagrams.  
   - Input: ['a', 'a', 'b', 'b']  
   - Output: [('a', 'a'), ('b', 'b')]  
5. **Mixed Case Handling**: If we want to handle mixed case (e.g., 'Listen' and 'Silent'), we should convert all strings to the same case before processing.

Detect anagram in array

Microsoft

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Microsoft Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string