Detect anagram in matrix

Question

Given a 2D matrix of characters and a string, write a function to determine if any of the rows or columns in the matrix contain an anagram of the given string. The function should return a boolean value indicating whether such an anagram exists.

Codemia · Accepted Answer

To determine if any row or column in a 2D matrix contains an anagram of a given string, we can leverage the concept of character frequency counting. An anagram is simply a rearrangement of characters, meaning two strings are anagrams if they contain the same characters with the same frequencies. This suggests that we can use a hash map (or dictionary) to store the frequency of each character in the target string. The two-pointer technique isn't directly applicable here since we need to evaluate multiple sequences (both rows and columns) for potential matches.

1. **Count Character Frequencies**: Create a frequency dictionary for the target string. For example, for the string 'abc', the dictionary would be {'a': 1, 'b': 1, 'c': 1}.
2. **Check Rows**: Iterate through each row of the matrix. For each row, create a frequency dictionary and compare it with the target string's frequency dictionary. If they match, return True.
3. **Check Columns**: If no matches are found in the rows, iterate through each column, constructing a frequency dictionary for each column in a similar manner and compare it with the target string's frequency dictionary. If a match is found, return True.
4. **Return False**: If neither rows nor columns contain an anagram of the string, return False.

Here is the Python code implementing the above approach:

```python
def detect_anagram_in_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

from collections import Counter
    target_count = Counter(target)
    rows, cols = len(matrix), len(matrix[0])

# Check each row
    for row in matrix:
        if Counter(row) == target_count:
            return True

# Check each column
    for col in range(cols):
        column_chars = ''.join(matrix[row][col] for row in range(rows))
        if Counter(column_chars) == target_count:
            return True

return False
```

The time complexity of this solution is O(n * m), where n is the number of rows and m is the number of columns in the matrix. This is because we traverse each row and each column once, calculating the frequency counts using O(k) time for each comparison, where k is the length of the target string. The space complexity is O(k) for the frequency dictionary storing the target's character counts. Since k is constant relative to n and m in terms of space, it can be considered O(1) for practical purposes.

1. If the matrix is empty (i.e., `matrix = []`), the function should return False because there are no rows or columns to check.
2. If the target string is empty (i.e., `target = ''`), it should also return False, as there can be no anagrams of an empty string in any row or column.
3. If the matrix contains only one character and matches the target string, it should return True. For instance, for `matrix = [['a']]` and `target = 'a'`, the output should be True.

Detect anagram in matrix

Uber

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

Uber 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