We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Match Alphanumerical Pattern in Matrix I

Number: 3385

Difficulty: Medium

Paid? Yes

Companies: Uber, Visa

Problem Description

Given a 2D integer matrix board and a 2D character matrix pattern, the task is to locate a submatrix in board that matches pattern. A match means that when digits in pattern remain the same, each letter in pattern can be mapped to a unique digit such that all occurrences of the same letter correspond to the same digit in the submatrix and different letters correspond to different digits. If the submatrix exists, return the coordinates [row, col] of its top-left corner; if multiple exist, choose the one with the smallest row, and then column. Otherwise, return [-1, -1].

Key Insights

  • Iterate over every possible submatrix in board that has the same dimensions as pattern.
  • For each candidate submatrix, maintain a mapping for letters to digits and a reverse mapping to enforce unique assignments.
  • For pattern digits (characters that are digits), directly compare with the corresponding board value.
  • For pattern letters, either assign a mapping (if not assigned) or check that the assigned digit matches, while ensuring that two distinct letters never map to the same digit.
  • Due to constraints (board and pattern sizes up to 50), a brute-force approach is acceptable.

Space and Time Complexity

Time Complexity: O((n - p + 1) * (m - q + 1) * (p * q)), where n, m are the dimensions of board and p, q are the dimensions of pattern. Space Complexity: O(1) extra space (only maps for letter-digit assignments, with at most 26 entries).

Solution

The solution iterates over every valid top-left coordinate in board where a submatrix of pattern dimensions can be extracted. For each candidate submatrix, the algorithm checks if it matches the pattern using two hash tables: one for mapping letters to digits and another for mapping digits back to letters, ensuring each letter maps to a unique digit. If all cells satisfy the rule (digits compare exactly when a digit is specified, and letters abide by the unique mapping condition), the submatrix is valid and its coordinates are returned. If none is found, [-1, -1] is returned.

Code Solutions

def match_submatrix(board, pattern, start_row, start_col):
    letter_to_digit = {}
    # Iterate over each cell in the pattern matrix.
    for i in range(len(pattern)):
        for j in range(len(pattern[0])):
            board_value = board[start_row + i][start_col + j]
            pat_char = pattern[i][j]
            if pat_char.isdigit():
                # If character is digit, verify it matches the board number.
                if int(pat_char) != board_value:
                    return False
            else:
                # If it is a letter, handle the mapping.
                if pat_char in letter_to_digit:
                    # If mapping exists, check for consistency.
                    if letter_to_digit[pat_char] != board_value:
                        return False
                else:
                    # Check that no other letter is mapped to this board_value.
                    if board_value in letter_to_digit.values():
                        return False
                    letter_to_digit[pat_char] = board_value
    return True

def findPattern(board, pattern):
    board_rows = len(board)
    board_cols = len(board[0])
    pat_rows = len(pattern)
    pat_cols = len(pattern[0])
    
    # Iterate over all possible starting positions for the pattern in board.
    for row in range(board_rows - pat_rows + 1):
        for col in range(board_cols - pat_cols + 1):
            if match_submatrix(board, pattern, row, col):
                return [row, col]
    return [-1, -1]

# Example usage:
board = [[1,2,2],[2,2,3],[2,3,3]]
pattern = ["ab", "bb"]
print(findPattern(board, pattern))  # Expected output: [0, 0]
← Back to All Questions