Find the Top-Left Submatrix Matching a Grid Pattern With Letter Variables

You are given a matrix of integers and a pattern grid with p rows and q columns. Each pattern cell is either a number, which must equal the matrix value it covers, or a lowercase letter, which stands for an unknown number: every cell holding the same letter must cover the same matrix value. Find a p x q submatrix of the matrix that matches the pattern and return the coordinate of its top-left cell. If several submatrices match, return the one with the lowest row index, and among those the lowest column index.

Function Signature

def find_pattern(matrix: list[list[int]], pattern: list[list[str]]) -> list[int]:

Rules

• Placing the pattern with its top-left cell at (r, c) lines up pattern[i][j] with matrix[r + i][c + j] for every 0 <= i < p and 0 <= j < q. The whole pattern must lie inside the matrix, and it is never rotated or reflected.
• A number cell is written as str(v) for an integer v (for example "5" or "-12") and matches only a matrix value equal to v.
• A letter cell matches any value, but within one placement all cells holding the same letter must cover equal values. Different letters are independent: they may cover equal or different values, and a letter may cover a value that also appears as a number cell.
• Return [r, c] for the matching placement with the smallest r, breaking ties by the smallest c. Return [-1, -1] if no placement matches.

Constraints

• 1 <= len(matrix) <= 50 and 1 <= len(matrix[0]) <= 50; all matrix rows have the same length.
• 1 <= p <= len(matrix) and 1 <= q <= len(matrix[0]); all pattern rows have length q.
• -10^9 <= matrix[i][j] <= 10^9
• Each pattern cell is either one lowercase letter from a to z, or str(v) for an integer -10^9 <= v <= 10^9.

Examples

Example 1

Input: matrix = [[7, 8, 4, 4],
 [6, 6, 5, 9],
 [5, 3, 5, 0]]
 pattern = [["x", "x"],
 ["5", "y"]]
Output: [0, 2]

At (0, 0) the two x cells cover 7 and 8, and at (0, 1) they cover 8 and 4, so both fail. At (0, 2) both x cells cover 4, the "5" cell covers 5, and y covers 9, so it matches. The placement at (1, 0) also matches (x covers 6 twice, "5" covers 5, y covers 3), but its row index is higher.

Example 2

Input: matrix = [[1, 1], [1, 1]], pattern = [["a", "b"]]
Output: [0, 0]

a and b both cover 1, which is allowed because different letters are independent.

Example 3

Input: matrix = [[1, 2, 3], [4, 5, 6]], pattern = [["a"], ["a"]]
Output: [-1, -1]

The three placements cover the pairs (1, 4), (2, 5) and (3, 6); none of them holds two equal values.