3078. Match Alphanumerical Pattern in Matrix I
Problem Description
The task is to find a submatrix within a given 2D integer matrix board
, which matches a specified 2D character pattern pattern
. The board
matrix contains integers ranging from 0 to 9, while the pattern
matrix consists of characters that may be digits or lowercase English letters.
A submatrix from the board
is said to match the pattern
if two main criteria are met:
- The dimensions of the
pattern
and the submatrix from theboard
are exactly the same. - Each cell in the
pattern
corresponds to the matching cell in the submatrix from theboard
.- If a cell in the
pattern
contains a digit, the corresponding cell in theboard
must contain the same digit. - If a cell in the
pattern
contains a letter, we are allowed to substitute the letter with any unique digit that ensures thepattern
still correlates to theboard
submatrix. Every occurrence of a particular letter must be replaced with the same digit in the submatrix, and different letters should map to different digits.
- If a cell in the
We need to return the coordinates (row and column index) of the upper-left corner of the matching submatrix or [-1, -1]
if no such submatrix exists. In cases where multiple solutions exist, we return the submatrix with the lowest row index, and if there's still a tie, we then consider the submatrix with the lowest column index.
Intuition
To solve this problem, we use an approach that compares each possible submatrix of the board
with the pattern
, starting from the smallest row and column indices. We iterate over the board
, attempting to match the pattern
. For each top-left corner of the board
that we consider (by selecting the starting row and column), we check if an r
(number of rows in pattern
) by c
(number of columns in pattern
) submatrix here can be a match for the pattern
.
During the checking process for each submatrix, we ensure that:
- If the current cell in the
pattern
is a digit, it must match exactly with the corresponding cell in the submatrix of theboard
. - If the current cell in the
pattern
is a letter, we track its correspondence with any digit in a way that no two different letters are mapped to the same digit, and the same letter is mapped consistently to the same digit across the entire submatrix.
We make use of two dictionaries to keep the mappings of pattern letters to board digits and vice versa. If at any point, a discrepancy is found (mismatched digits or conflicting mappings), we know the current submatrix can't be a match, and we proceed to the next potential top-left corner of the submatrix.
Once we find a submatrix that matches the pattern
, we return its top-left coordinates. If no matching submatrix is found after iterating through all possible submatrices, we return [-1, -1]
.
Solution Approach
The provided solution is an enumeration approach. Essentially, the idea is to systematically consider every possible starting position for a submatrix in board
that could potentially match the pattern
.
Here is the breakdown of the implementation steps:
-
Coordinates Iteration:
- We calculate the dimensions
m
andn
of theboard
, andr
andc
for thepattern
. - Then, we iterate over every possible top-left corner
(i, j)
for anr
byc
submatrix within theboard
. The iteration stops atm - r + 1
for rows andn - c + 1
for columns to prevent overflow (i.e., we don't start a submatrix check that goes beyond the bounds ofboard
).
- We calculate the dimensions
-
Submatrix Matching:
- For each potential top-left corner, we call the
check
function, which attempts to match the submatrix inboard
starting at(i, j)
with thepattern
. - The
check
function uses two dictionaries,d1
andd2
, to map letters inpattern
to digits inboard
and vice versa.d1
maps pattern letters to board digits, andd2
maps board digits to pattern letters.
- For each potential top-left corner, we call the
-
Mapping Integrity:
- During the match check, if
pattern[a][b]
is a digit, we simply compare it to the corresponding cell inboard
and returnFalse
if there's a mismatch (meaning this submatrix does not match thepattern
). - If
pattern[a][b]
is a letter, we must consider the following two scenarios:- If the letter has been seen before (exists in
d1
), we must ensure the current cell inboard
matches the previously mapped digit. If not, returnFalse
. - Similar checks are done in
d2
, where if the digit in board is already mapped to a different letter, we also returnFalse
.
- If the letter has been seen before (exists in
- If neither condition violates the mapping, we update
d1
andd2
with the new mapping between the letter and the digit.
- During the match check, if
-
Returning the Result:
- If the
check
function returnsTrue
, thefindPattern
function immediately returns the top-left coordinates[i, j]
of the submatrix as this is the first match found. - If we go through all potential top-left corners and never return
[i, j]
, this means no matching submatrix was found, and we therefore return[-1, -1]
.
- If the
The overall time complexity of the solution is determined by the total number of submatrices we check, which is (m - r + 1) * (n - c + 1)
, and the time taken to validate each submatrix, which can be up to r * c
for comparing with the pattern
. This makes the overall time complexity O((m - r + 1) * (n - c + 1) * r * c)
, which is acceptable given the constraints of the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Assume we have the following board
and pattern
:
1board: 21 2 3 33 4 5 45 6 7 5 6pattern: 7"a 5" 8"5 b"
For our example, m
and n
(the dimensions of board
) are both 3, and r
and c
(the dimensions of pattern
) are both 2. Given this, we will check potential submatrices of board
to see if they match pattern
. Since our pattern has dimensions 2x2, our checks will begin with the top row of board
and only need to consider the first two rows and columns as potential starting points.
Step 1: Coordinates Iteration
- We start by iterating from the top-left corner of the
board
. The first potential top-left corner is(0, 0)
.
Step 2: Submatrix Matching
-
We look at the submatrix of
board
given by the top-left corner(0, 0)
:11 2 23 4
-
Then we compare it with
pattern
.pattern[0][0]
contains a letter 'a', which we have not encountered before, so we can let 'a' be any digit (here it would match with '1').pattern[1][0]
contains a digit '5', but there is a '3' at the corresponding position inboard
, so this submatrix is not a match. We move to the next possible top-left corner. -
The next potential top-left corner is
(0, 1)
. The submatrix fromboard
at(0, 1)
is:12 3 24 5
-
Comparing with
pattern
,pattern[0][1]
is '5', and it matches the '5' in the submatrix ofboard
. So far, the submatrix could potentially be a match.
Step 3: Mapping Integrity
-
We continue the comparison with the rest of the cells:
pattern[1][1]
is 'b', which has not been seen before. So, 'b' can take the value of '4', and our current mapping would be 'a' -> '2', 'b' -> '4'.- However, looking at the
pattern[1][0]
, we see '5', which should be the same as the digit inboard
at(1, 0)
given our current top-left corner(0, 1)
. However, at this position inboard
we have '4'. This does not match our required '5' to meet the condition ofpattern[1][0]
, so again, this submatrix is not a match.
-
The last potential top-left corner for our submatrix in
board
is(1, 0)
. The submatrix fromboard
at(1, 0)
is:13 4 25 6
-
This is the submatrix matching phase for this position:
pattern[0][0]
is 'a', which can correspond to '3'.pattern[0][1]
is '5', and it matches the '5' inboard
.pattern[1][0]
is '5', which also matches the '5' inboard
.pattern[1][1]
is 'b', which can correspond to '6' (different from 'a' -> '3').
With this mapping, 'a' -> '3' and 'b' -> '6', the entire submatrix matches the
pattern
.
Step 4: Returning the Result
- Since we've found a matching submatrix in
board
that corresponds to ourpattern
for the top-left position(1, 0)
, we return these coordinates[1, 0]
as the answer.
If no matching submatrix had been found, the result would have been [-1, -1]
. But in our example, we successfully matched the pattern, so the top-left corner of the matching submatrix is indeed [1, 0]
.
Solution Implementation
1class Solution:
2 def findPattern(self, board: List[List[int]], pattern: List[str]) -> List[int]:
3 # This function checks if the pattern matches the board
4 # starting at board position (start_row, start_col)
5 def is_match(start_row: int, start_col: int) -> bool:
6 char_to_num = {} # Maps pattern characters to board numbers
7 num_to_char = {} # Maps board numbers to pattern characters
8
9 # Iterate over each cell in the pattern
10 for row in range(pattern_rows):
11 for col in range(pattern_cols):
12 board_row, board_col = start_row + row, start_col + col
13 if pattern[row][col].isdigit():
14 # If the pattern cell is a digit, check if it matches the board cell
15 if int(pattern[row][col]) != board[board_row][board_col]:
16 return False
17 else:
18 # If the pattern cell is not a digit (assumed to be a variable)
19 if pattern[row][col] in char_to_num and char_to_num[pattern[row][col]] != board[board_row][board_col]:
20 return False
21 if board[board_row][board_col] in num_to_char and num_to_char[board[board_row][board_col]] != pattern[row][col]:
22 return False
23 # Record the mapping between the pattern variable and the board number
24 char_to_num[pattern[row][col]] = board[board_row][board_col]
25 num_to_char[board[board_row][board_col]] = pattern[row][col]
26 # If no conflicts found, pattern matches
27 return True
28
29 # Size of the board
30 board_rows, board_cols = len(board), len(board[0])
31 # Size of the pattern to look for
32 pattern_rows, pattern_cols = len(pattern), len(pattern[0])
33
34 # Iterate over each possible starting position in the board
35 for row in range(board_rows - pattern_rows + 1):
36 for col in range(board_cols - pattern_cols + 1):
37 # If a match is found at the current starting position, return the position
38 if is_match(row, col):
39 return [row, col]
40
41 # If no match is found, return indicator of failure
42 return [-1, -1]
43
1class Solution {
2 // Function to find the top-left coordinate of the pattern in the board
3 public int[] findPattern(int[][] board, String[] pattern) {
4 int rows = board.length, cols = board[0].length;
5 int patternRows = pattern.length, patternCols = pattern[0].length();
6
7 // Iterate over the board with the dimensions of the pattern to check for a match
8 for (int i = 0; i <= rows - patternRows; ++i) {
9 for (int j = 0; j <= cols - patternCols; ++j) {
10 // If a match is found, return the top-left coordinate
11 if (isPatternMatch(board, pattern, i, j)) {
12 return new int[] {i, j};
13 }
14 }
15 }
16 // If no match is found, return {-1, -1}
17 return new int[] {-1, -1};
18 }
19
20 // Helper method to check if the pattern matches the board at the given top left corner (i, j)
21 private boolean isPatternMatch(int[][] board, String[] pattern, int i, int j) {
22 int[] letterToNumberMapping = new int[26]; // Mapping from letter to number
23 int[] numberToLetterMapping = new int[10]; // Mapping from number to letter
24 Arrays.fill(letterToNumberMapping, -1);
25 Arrays.fill(numberToLetterMapping, -1);
26
27 // Iterate over each character of the pattern
28 for (int a = 0; a < patternRows; ++a) {
29 for (int b = 0; b < patternCols; ++b) {
30 int x = i + a, y = j + b; // Get the corresponding coordinates on the board
31
32 // If the character is a digit, check if it matches the board's number
33 if (Character.isDigit(pattern[a].charAt(b))) {
34 int value = pattern[a].charAt(b) - '0';
35 if (value != board[x][y]) {
36 return false; // Digit does not match
37 }
38 } else {
39 // If character is a letter, check if a consistent mapping exists
40 int letterIndex = pattern[a].charAt(b) - 'a';
41 if (letterToNumberMapping[letterIndex] != -1 && letterToNumberMapping[letterIndex] != board[x][y]) {
42 return false; // Previous mapping does not match current number
43 }
44 if (numberToLetterMapping[board[x][y]] != -1 && numberToLetterMapping[board[x][y]] != letterIndex) {
45 return false; // Previous mapping does not match current letter
46 }
47 // Create a mapping from letter to number and number to letter
48 letterToNumberMapping[letterIndex] = board[x][y];
49 numberToLetterMapping[board[x][y]] = letterIndex;
50 }
51 }
52 }
53 return true; // Pattern matches the board
54 }
55}
56
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 vector<int> findPattern(vector<vector<int>>& board, vector<string>& patterns) {
8 // Dimensions of the board and the pattern
9 int rowsBoard = board.size(), colsBoard = board[0].size();
10 int rowsPattern = patterns.size(), colsPattern = patterns[0].size();
11
12 // Lambda function to check if pattern matches with board starting at (startRow, startCol)
13 auto isMatch = [&](int startRow, int startCol) {
14 vector<int> digitToCharMap(26, -1); // Maps digits in pattern to characters
15 vector<int> charToDigitMap(10, -1); // Maps characters in board to digits in pattern
16
17 // Check every position in pattern
18 for (int row = 0; row < rowsPattern; ++row) {
19 for (int col = 0; col < colsPattern; ++col) {
20 int boardRow = startRow + row, boardCol = startCol + col;
21
22 if (isdigit(patterns[row][col])) {
23 // If the pattern has a digit, it must match the board's number directly
24 int value = patterns[row][col] - '0';
25 if (value != board[boardRow][boardCol]) {
26 return false; // Mismatch found
27 }
28 } else {
29 // If the pattern has a character, it represents any digit
30 int patternVal = patterns[row][col] - 'a';
31 if (digitToCharMap[patternVal] != -1 && digitToCharMap[patternVal] != board[boardRow][boardCol]) {
32 return false; // Mismatch with previous mapping
33 }
34 if (charToDigitMap[board[boardRow][boardCol]] != -1 && charToDigitMap[board[boardRow][boardCol]] != patternVal) {
35 return false; // Conflicting mapping found
36 }
37 // Update the mappings for the current character and digit
38 digitToCharMap[patternVal] = board[boardRow][boardCol];
39 charToDigitMap[board[boardRow][boardCol]] = patternVal;
40 }
41 }
42 }
43 return true; // No mismatches found, pattern matches
44 };
45
46 // Iterate over every starting position on the board where the pattern could fit
47 for (int i = 0; i < rowsBoard - rowsPattern + 1; ++i) {
48 for (int j = 0; j < colsBoard - colsPattern + 1; ++j) {
49 if (isMatch(i, j)) {
50 // Pattern found, return top-left position where it matches
51 return {i, j};
52 }
53 }
54 }
55
56 // If no matching position is found, return {-1, -1}
57 return {-1, -1};
58 }
59};
60
1function findPattern(board: number[][], pattern: string[]): number[] {
2 const boardRows: number = board.length;
3 const boardCols: number = board[0].length;
4 const patternRows: number = pattern.length;
5 const patternCols: number = pattern[0].length;
6
7 // Helper function to check if pattern matches with the board starting at (rowStart, colStart).
8 const isMatchAtPosition = (rowStart: number, colStart: number): boolean => {
9 const letterToNumberMap: number[] = Array(26).fill(-1); // Maps letters to numbers
10 const numberToLetterMap: number[] = Array(10).fill(-1); // Maps numbers to letters
11
12 for (let rowDelta = 0; rowDelta < patternRows; ++rowDelta) {
13 for (let colDelta = 0; colDelta < patternCols; ++colDelta) {
14 const boardRow: number = rowStart + rowDelta;
15 const boardCol: number = colStart + colDelta;
16
17 // If current character in pattern is a number.
18 if (!isNaN(Number(pattern[rowDelta][colDelta]))) {
19 const numValue: number = Number(pattern[rowDelta][colDelta]);
20 if (numValue !== board[boardRow][boardCol]) {
21 return false;
22 }
23 } else {
24 // Calculate the index for the character in the alphabet (0 for 'a', 1 for 'b', etc.)
25 const letterIndex: number = pattern[rowDelta].charCodeAt(colDelta) - 'a'.charCodeAt(0);
26 if (letterToNumberMap[letterIndex] !== -1 && letterToNumberMap[letterIndex] !== board[boardRow][boardCol]) {
27 return false;
28 }
29 if (numberToLetterMap[board[boardRow][boardCol]] !== -1 && numberToLetterMap[board[boardRow][boardCol]] !== letterIndex) {
30 return false;
31 }
32 letterToNumberMap[letterIndex] = board[boardRow][boardCol];
33 numberToLetterMap[board[boardRow][boardCol]] = letterIndex;
34 }
35 }
36 }
37 return true;
38 };
39
40 // Iterate over board to find the first matching position.
41 for (let row = 0; row <= boardRows - patternRows; ++row) {
42 for (let col = 0; col <= boardCols - patternCols; ++col) {
43 if (isMatchAtPosition(row, col)) {
44 return [row, col]; // Return the starting position of the match
45 }
46 }
47 }
48 return [-1, -1]; // Return [-1, -1] if no match is found
49}
50
Time and Space Complexity
The time complexity of the provided code is O(m * n * r * c)
. This is calculated by considering that the code must check every submatrix starting at all positions (i, j)
in the board
, where i
ranges from 0
to m - r
and j
ranges from 0
to n - c
. For each of these positions, it must compare an r x c
submatrix pattern with the corresponding section of the board, which takes O(r * c)
time.
The space complexity of the code is O(Σ)
, where Σ
denotes the set of unique characters used to represent the digits and the lowercase letters in the pattern. Since the pattern includes only digits 0-9
and lowercase letters a-z
, the maximum size of Σ
is 36 (10
digits + 26
letters). This space is used to store the mappings between the pattern characters and board numbers, once in d1
for mapping from the pattern to the board and once in d2
for mapping from the board to the pattern. Therefore, the space complexity is O(36)
or simply O(1)
since 36 is a constant and does not grow with the input size.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.