3078. Match Alphanumerical Pattern in Matrix I

Medium
Leetcode Link

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:

  1. The dimensions of the pattern and the submatrix from the board are exactly the same.
  2. Each cell in the pattern corresponds to the matching cell in the submatrix from the board.
    • If a cell in the pattern contains a digit, the corresponding cell in the board 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 the pattern still correlates to the board 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.

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 the board.
  • 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].

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

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:

  1. Coordinates Iteration:

    • We calculate the dimensions m and n of the board, and r and c for the pattern.
    • Then, we iterate over every possible top-left corner (i, j) for an r by c submatrix within the board. The iteration stops at m - r + 1 for rows and n - c + 1 for columns to prevent overflow (i.e., we don't start a submatrix check that goes beyond the bounds of board).

  2. Submatrix Matching:

    • For each potential top-left corner, we call the check function, which attempts to match the submatrix in board starting at (i, j) with the pattern.
    • The check function uses two dictionaries, d1 and d2, to map letters in pattern to digits in board and vice versa. d1 maps pattern letters to board digits, and d2 maps board digits to pattern letters.

  3. Mapping Integrity:

    • During the match check, if pattern[a][b] is a digit, we simply compare it to the corresponding cell in board and return False if there's a mismatch (meaning this submatrix does not match the pattern).
    • 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 in board matches the previously mapped digit. If not, return False.
      • Similar checks are done in d2, where if the digit in board is already mapped to a different letter, we also return False.
    • If neither condition violates the mapping, we update d1 and d2 with the new mapping between the letter and the digit.

  4. Returning the Result:

    • If the check function returns True, the findPattern 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].

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example 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 in board, 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 from board at (0, 1) is:

    12 3
24 5

  • Comparing with pattern, pattern[0][1] is '5', and it matches the '5' in the submatrix of board. 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 in board at (1, 0) given our current top-left corner (0, 1). However, at this position in board we have '4'. This does not match our required '5' to meet the condition of pattern[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 from board 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' in board.
    • pattern[1][0] is '5', which also matches the '5' in board.
    • 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 our pattern 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
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫