Find the Earliest Matrix Match for a Digit-and-Letter Pattern
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Find the Earliest Matrix Match for a Digit-and-Letter Pattern
You are given an integer matrix `board` whose entries are digits `0..9`, and a rectangular pattern represented as an array of strings. Each pattern character is a digit or a lowercase English letter.
A contiguous board submatrix matches the pattern when it has the same dimensions and satisfies all these rules:
- A literal digit in the pattern must equal the corresponding board value.
- Every occurrence of the same letter must correspond to the same board value.
- Different letters must correspond to different board values.
- A letter's value must differ from every literal digit appearing anywhere in the pattern. More generally, a letter position must have a different value from every position with a different pattern symbol.
The letter assignment may be chosen independently for each candidate submatrix. Return `[row,column]` for the upper-left corner of a matching submatrix. If several match, choose the lowest row first, then the lowest column within that row. Return `[-1,-1]` if none matches.
### Examples
**Example 1**
```text
Input: board = [[7,7,4,7],[3,7,4,7]], pattern = ["a7"]
Output: [0,2]
```
The two cells at `(0,0)` are `[7,7]`, which do not match: the letter `a` cannot use the literal digit `7`. The cells at `(0,2)` are `[4,7]`, matching with `a = 4`. A match also starts at `(1,0)`, but row zero takes priority even though its matching column is larger.
**Example 2**
```text
Input: board = [[2,2],[5,5]], pattern = ["ab"]
Output: [-1,-1]
```
Each candidate row contains two equal values. Distinct letters `a` and `b` must use different values, so neither candidate matches.
### Constraints
- The board has between `1` and `50` rows and between `1` and `50` columns.
- `0 <= board[i][j] <= 9`.
- The pattern has between `1` and `50` rows and between `1` and `50` columns.
- Each pattern entry is a digit character `'0'..'9'` or a lowercase English letter.
### Clarifying Questions
- Can one letter change its value between positions in the same candidate? No.
- Can a letter reuse the digit shown by a literal pattern character? No, even when the literal appears later in the pattern.
- Can the same literal digit appear at several positions? Yes; those positions must all equal that digit.
- Can a letter have a different value in a different candidate submatrix? Yes; matching is checked independently for each candidate.
- What if the pattern is taller or wider than the board? No submatrix fits, so return `[-1,-1]`.
### C++ Interface
```cpp
class Solution {
public:
vector<int> findPattern(vector<vector<int>>& board, vector<string>& pattern) {
}
};
```
### Reasoning Checkpoints
- Enforce literal digits, consistent repeated letters, and distinct values for different pattern symbols.
- Apply the row-first, column-second coordinate priority and the exact no-match result.
- Cover candidate boundaries and justify correctness and resource use for the full dimensions.
```hint Validate one candidate with fresh assignments
List the literal digits used anywhere in the pattern. For each candidate, keep both a letter-to-digit assignment and which letter owns each digit; start those assignments fresh. Examine candidate upper-left coordinates in row-major order.
```
Overview: Find the earliest board submatrix satisfying a digit-and-letter pattern, including literal-digit exclusions, consistent letters and exact coordinate priority.