Match Alphanumerical Pattern in Matrix I

Medium

Visa

0 views

Topics:

ArraysStrings

You are given a matrix matrix of characters and a string pattern consisting of alphanumeric characters.

Return true if the pattern exists in the matrix and false otherwise.

The pattern can be matched in 8-directions starting from any cell in the matrix. The 8 directions are up, down, left, right and the 4 diagonal directions. The matching should not visit one cell more than once.

Example 1:


Input: matrix = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], pattern = "ABCCED"
Output: true
Explanation:
The pattern "ABCCED" exists in the matrix starting from matrix[0][0].

Example 2:


Input: matrix = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], pattern = "SEE"
Output: true
Explanation:
The pattern "SEE" exists in the matrix starting from matrix[2][3].

Example 3:


Input: matrix = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], pattern = "ABCB"
Output: false
Explanation:
The pattern "ABCB" does not exist in the matrix because the backtracking would not allow visiting the same cell twice.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
1 <= pattern.length <= 200
matrix and pattern consist of alphanumeric characters.

Match Alphanumerical Pattern in Matrix I

Medium

Visa

0 views

Topics:

ArraysStrings

You are given a matrix matrix of characters and a string pattern consisting of alphanumeric characters.

Return true if the pattern exists in the matrix and false otherwise.

The pattern can be matched in 8-directions starting from any cell in the matrix. The 8 directions are up, down, left, right and the 4 diagonal directions. The matching should not visit one cell more than once.

Example 1:


Input: matrix = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], pattern = "ABCCED"
Output: true
Explanation:
The pattern "ABCCED" exists in the matrix starting from matrix[0][0].

Example 2:


Input: matrix = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], pattern = "SEE"
Output: true
Explanation:
The pattern "SEE" exists in the matrix starting from matrix[2][3].

Example 3:


Input: matrix = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], pattern = "ABCB"
Output: false
Explanation:
The pattern "ABCB" does not exist in the matrix because the backtracking would not allow visiting the same cell twice.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
1 <= pattern.length <= 200
matrix and pattern consist of alphanumeric characters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the maximum length of the alphanumeric pattern string?
Can the alphanumeric pattern wrap around the matrix (e.g., from the last column back to the first) or diagonally?
What characters are allowed in the alphanumeric pattern string and in the matrix cells (e.g., only uppercase letters, only digits, mixed)?
If the pattern is not found, what should I return (e.g., `null`, an empty list, a boolean `false`)?
Should the pattern match be case-sensitive?

Brute Force Solution

Approach

The brute force approach to finding a pattern in a matrix is like meticulously checking every possible starting point and direction within the matrix. We'll try to match the pattern from each position, moving in all possible directions until we either find a match or exhaust all possibilities. It's an exhaustive search, guaranteeing we'll find the pattern if it exists.

Here's how the algorithm would work step-by-step:

Start at the very first position in the matrix.
See if the beginning of the pattern matches the character in that position.
If it does, try to match the rest of the pattern by looking at adjacent positions in every possible direction (up, down, left, right, and diagonals).
If at any point the pattern doesn't match the matrix, abandon that starting position and direction.
Move to the next position in the matrix and repeat the process.
Keep doing this until you've checked every single position in the matrix as a potential starting point.
If the entire pattern is found at any of these starting positions, you have a match.

Code Implementation

def find_pattern_brute_force(matrix, pattern):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0]) if number_of_rows > 0 else 0
    pattern_length = len(pattern)

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            # Check if the current cell matches the start of pattern
            if matrix[row_index][column_index] == pattern[0]:

                # Explore all possible directions
                for row_direction, column_direction in [
                    (-1, 0), (1, 0), (0, -1), (0, 1),
                    (-1, -1), (-1, 1), (1, -1), (1, 1)
                ]:
                    
                    match_found = True
                    
                    # Verify pattern continues in given direction
                    for pattern_index in range(1, pattern_length):
                        next_row = row_index + pattern_index * row_direction
                        next_column = column_index + pattern_index * column_direction
                        
                        # Check matrix boundaries and pattern match
                        if (
                            next_row < 0 or next_row >= number_of_rows or
                            next_column < 0 or next_column >= number_of_columns or
                            matrix[next_row][next_column] != pattern[pattern_index]
                        ):
                            match_found = False
                            break

                    # Pattern found in this direction
                    if match_found:
                        return True

    # Exhausted all positions and directions
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m * n * 8^k) – Let m be the number of rows and n be the number of columns in the matrix, and k be the length of the pattern. We iterate through each cell in the matrix as a potential starting point, contributing a factor of m * n. From each starting cell, we explore all possible directions (8 directions: up, down, left, right, and the four diagonals) to match the pattern. In the worst case, for each character in the pattern (of length k), we have 8 choices of direction. This leads to a branching factor of 8 for each character in the pattern, giving us 8^k. Therefore, the overall time complexity is O(m * n * 8^k).

Space Complexity

O(1) – The described brute force approach iterates through the matrix and checks for pattern matches at each position. It doesn't explicitly mention any auxiliary data structures like lists, sets, or hash maps for storing intermediate results or visited locations. The algorithm appears to use a constant amount of extra space for variables to track the current position and potentially the direction being checked, regardless of the size of the matrix (N). Thus, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem involves finding a specific pattern of letters and numbers within a grid. The trick to solving it efficiently is to avoid checking every single possible spot in the grid and instead focus on areas where the pattern is most likely to start. We essentially prune our search based on the characteristics of the pattern.

Here's how the algorithm would work step-by-step:

First, examine the pattern you are searching for. Look for any specific characters or sequences that are relatively rare or unique within the grid.
Instead of starting your search at the very beginning of the grid, jump directly to the places where you find these rare or unique parts of the pattern. This immediately eliminates a lot of unnecessary searching.
Once you find a potential starting point, carefully check the surrounding cells to see if they match the rest of the pattern in the correct order and direction.
If the surrounding cells don't match, quickly move on to the next potential starting point based on the rare/unique characters.
If the surrounding cells do match, you've found an instance of the pattern! You can then continue searching for other possible instances if needed, again prioritizing locations with those distinctive characters.

Code Implementation

def find_pattern_in_matrix(matrix, pattern):
    rows = len(matrix)
    cols = len(matrix[0])
    pattern_rows = len(pattern)
    pattern_cols = len(pattern[0])

    if pattern_rows > rows or pattern_cols > cols:
        return False

    # Focusing search where unique chars appear.
    for row_index in range(rows - pattern_rows + 1):
        for col_index in range(cols - pattern_cols + 1):
            if matrix[row_index][col_index] == pattern[0][0]:

                match = True

                # Verifying surrounding pattern.
                for pattern_row_index in range(pattern_rows):
                    for pattern_col_index in range(pattern_cols):
                        if matrix[row_index + pattern_row_index][col_index + pattern_col_index] != pattern[pattern_row_index][pattern_col_index]:
                            match = False
                            break
                    if not match:
                        break

                if match:
                    return True

    # No pattern found.
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – Let m be the number of cells in the matrix matching the rare/unique character sequence of the pattern, and n be the number of cells required to verify the entire pattern once a potential starting cell is found. The algorithm efficiently prunes the search space, only checking for the full pattern starting at cells that match the unique sequence. In the worst case, we might need to verify the entire pattern from each of these m potential starting positions. Therefore, the time complexity is approximately O(m*n). If m is proportional to the size of the matrix, the overall complexity would approach O(N) where N is the size of the matrix. However, the problem is explicitly asking for an explanation based on the count of cells, so we provide O(m*n).

Space Complexity

O(1) – The algorithm described focuses on identifying unique characters within the pattern and checking surrounding cells. It does not mention storing intermediate results, gathering items into a pile, or keeping track of visited locations. Therefore, only a constant amount of extra memory is needed to store variables like the current position being checked, irrespective of the grid's dimensions (N). Hence the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty matrix	Return an empty list immediately as there's no matrix to search within.
Null or empty pattern string	Return an empty list immediately as there's no pattern to match.
Matrix with zero rows or zero columns	Return an empty list as a zero-sized matrix cannot contain the pattern.
Pattern length exceeds the dimensions of the matrix	Return an empty list as the matrix is too small to contain the pattern.
Pattern contains characters not present in the matrix	The algorithm should correctly skip paths that lead to non-existent characters.
Pattern appears multiple times in the matrix (overlapping or non-overlapping)	The algorithm should find and return all the possible starting coordinates for a matching pattern.
Pattern is longer than the longest possible path in the matrix (cycle)	Implement a visited set or boolean matrix to prevent infinite recursion or looping.
Large matrix with very long pattern string exceeding memory constraints	Consider using iterative approach with limited search depth to prevent stack overflow, or optimize memory usage by pruning unnecessary paths.