You are given a 2D integer matrix board and a 2D character matrix pattern. Where 0 <= board[r][c] <= 9 and each element of pattern is either a digit or a lowercase English letter.
Your task is to find a submatrix of board that matches pattern.
An integer matrix part matches pattern if we can replace cells containing letters in pattern with some digits (each distinct letter with a unique digit) in such a way that the resulting matrix becomes identical to the integer matrix part. In other words,
pattern[r][c] is a digit, then part[r][c] must be the same digit.pattern[r][c] is a letter x:
pattern[i][j] == x, part[i][j] must be the same as part[r][c].pattern[i][j] != x, part[i][j] must be different than part[r][c].Return an array of length 2 containing the row number and column number of the upper-left corner of a submatrix of board which matches pattern. If there is more than one such submatrix, return the coordinates of the submatrix with the lowest row index, and in case there is still a tie, return the coordinates of the submatrix with the lowest column index. If there are no suitable answers, return [-1, -1].
Example 1:
| 1 | 2 | 2 |
| 2 | 2 | 3 |
| 2 | 3 | 3 |
| a | b |
| b | b |
Input: board = [[1,2,2],[2,2,3],[2,3,3]], pattern = ["ab","bb"]
Output: [0,0]
Explanation: If we consider this mapping: "a" -> 1 and "b" -> 2; the submatrix with the upper-left corner (0,0) is a match as outlined in the matrix above.
Note that the submatrix with the upper-left corner (1,1) is also a match but since it comes after the other one, we return [0,0].
Example 2:
| 1 | 1 | 2 |
| 3 | 3 | 4 |
| 6 | 6 | 6 |
| a | b |
| 6 | 6 |
Input: board = [[1,1,2],[3,3,4],[6,6,6]], pattern = ["ab","66"]
Output: [1,1]
Explanation: If we consider this mapping: "a" -> 3 and "b" -> 4; the submatrix with the upper-left corner (1,1) is a match as outlined in the matrix above.
Note that since the corresponding values of "a" and "b" must differ, the submatrix with the upper-left corner (1,0) is not a match. Hence, we return [1,1].
Example 3:
| 1 | 2 |
| 2 | 1 |
| x | x |
Input: board = [[1,2],[2,1]], pattern = ["xx"]
Output: [-1,-1]
Explanation: Since the values of the matched submatrix must be the same, there is no match. Hence, we return [-1,-1].
Constraints:
1 <= board.length <= 501 <= board[i].length <= 500 <= board[i][j] <= 91 <= pattern.length <= 501 <= pattern[i].length <= 50pattern[i][j] is either a digit represented as a string or a lowercase English letter.Problem Overview: You are given a character matrix and an alphanumerical pattern string. The goal is to determine whether the pattern can match a contiguous segment in any row of the matrix such that the mapping between pattern characters and matrix characters is consistent. Each symbol in the pattern must map to exactly one matrix character, and different symbols cannot map to the same character.
Approach 1: Enumeration with Bidirectional Hash Mapping (O(m * n * k) time, O(k) space)
The direct strategy is to enumerate every possible starting position in the matrix where the pattern could fit. For each row i and column j, attempt to match the pattern against the substring of length k. While scanning the characters, maintain two hash tables: one mapping pattern symbols to matrix characters and another mapping matrix characters back to pattern symbols. This enforces a bijection so that repeated pattern symbols always map to the same matrix character and no two pattern symbols map to the same value.
During verification, iterate through the pattern and the candidate substring simultaneously. On each step, check the mapping in both hash tables. If a conflict appears, stop early and move to the next starting position. If the entire pattern is processed without conflicts, a valid match exists and the search can terminate.
This approach works well because the pattern length is typically much smaller than the total matrix size. The algorithm performs a bounded verification for each candidate position. The logic is straightforward and relies heavily on fast hash lookups.
From a structural perspective, the solution combines iteration over a matrix, substring comparison from string processing, and hash-based consistency checks. The key insight is enforcing the bijection using two maps rather than one, which guarantees correctness even when repeated characters appear in either the pattern or the matrix segment.
Recommended for interviews: The enumeration with bidirectional hash maps is the expected approach. A brute-force comparison without mapping fails when repeated pattern symbols must correspond to the same character. Demonstrating the bijection using two hash tables shows solid understanding of pattern matching problems and is the standard technique interviewers look for.
Let's denote m and n as the number of rows and columns in the matrix board, and r and c as the number of rows and columns in the matrix pattern.
We can enumerate each possible sub-matrix's top-left position (i, j) in the board from small to large, and then determine whether the r times c sub-matrix with (i, j) as the top-left corner matches pattern. If we find a matching sub-matrix, we return (i, j). Otherwise, we return (-1, -1).
The time complexity is O(m times n times r times c), where m and n are the number of rows and columns in the matrix board, and r and c are the number of rows and columns in the matrix pattern. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this problem, \Sigma includes numbers and lowercase letters, so |\Sigma| leq 36.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive substring comparison | O(m * n * k) | O(1) | When pattern uniqueness constraints are ignored or for quick baseline testing |
| Enumeration with bidirectional hash maps | O(m * n * k) | O(k) | General solution ensuring a bijection between pattern symbols and matrix characters |
3078. Match Alphanumerical Pattern in Matrix I (Leetcode Medium) • Programming Live with Larry • 413 views views
Practice Match Alphanumerical Pattern in Matrix I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor