Skip to content

3078. Match Alphanumerical Pattern in Matrix I πŸ”’

Description

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,

  • The matrices have identical dimensions.
  • If pattern[r][c] is a digit, then part[r][c] must be the same digit.
  • If pattern[r][c] is a letter x:
    • For every pattern[i][j] == x, part[i][j] must be the same as part[r][c].
    • For every 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 <= 50
  • 1 <= board[i].length <= 50
  • 0 <= board[i][j] <= 9
  • 1 <= pattern.length <= 50
  • 1 <= pattern[i].length <= 50
  • pattern[i][j] is either a digit represented as a string or a lowercase English letter.

Solutions

Solution 1: Enumeration

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$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def findPattern(self, board: List[List[int]], pattern: List[str]) -> List[int]:
        def check(i: int, j: int) -> bool:
            d1 = {}
            d2 = {}
            for a in range(r):
                for b in range(c):
                    x, y = i + a, j + b
                    if pattern[a][b].isdigit():
                        if int(pattern[a][b]) != board[x][y]:
                            return False
                    else:
                        if pattern[a][b] in d1 and d1[pattern[a][b]] != board[x][y]:
                            return False
                        if board[x][y] in d2 and d2[board[x][y]] != pattern[a][b]:
                            return False
                        d1[pattern[a][b]] = board[x][y]
                        d2[board[x][y]] = pattern[a][b]
            return True

        m, n = len(board), len(board[0])
        r, c = len(pattern), len(pattern[0])
        for i in range(m - r + 1):
            for j in range(n - c + 1):
                if check(i, j):
                    return [i, j]
        return [-1, -1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int[] findPattern(int[][] board, String[] pattern) {
        int m = board.length, n = board[0].length;
        int r = pattern.length, c = pattern[0].length();
        for (int i = 0; i < m - r + 1; ++i) {
            for (int j = 0; j < n - c + 1; ++j) {
                if (check(board, pattern, i, j)) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {-1, -1};
    }

    private boolean check(int[][] board, String[] pattern, int i, int j) {
        int[] d1 = new int[26];
        int[] d2 = new int[10];
        Arrays.fill(d1, -1);
        Arrays.fill(d2, -1);
        for (int a = 0; a < pattern.length; ++a) {
            for (int b = 0; b < pattern[0].length(); ++b) {
                int x = i + a, y = j + b;
                if (Character.isDigit(pattern[a].charAt(b))) {
                    int v = pattern[a].charAt(b) - '0';
                    if (v != board[x][y]) {
                        return false;
                    }
                } else {
                    int v = pattern[a].charAt(b) - 'a';
                    if (d1[v] != -1 && d1[v] != board[x][y]) {
                        return false;
                    }
                    if (d2[board[x][y]] != -1 && d2[board[x][y]] != v) {
                        return false;
                    }
                    d1[v] = board[x][y];
                    d2[board[x][y]] = v;
                }
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<int> findPattern(vector<vector<int>>& board, vector<string>& pattern) {
        int m = board.size(), n = board[0].size();
        int r = pattern.size(), c = pattern[0].size();
        auto check = [&](int i, int j) {
            vector<int> d1(26, -1);
            vector<int> d2(10, -1);
            for (int a = 0; a < r; ++a) {
                for (int b = 0; b < c; ++b) {
                    int x = i + a, y = j + b;
                    if (isdigit(pattern[a][b])) {
                        int v = pattern[a][b] - '0';
                        if (v != board[x][y]) {
                            return false;
                        }
                    } else {
                        int v = pattern[a][b] - 'a';
                        if (d1[v] != -1 && d1[v] != board[x][y]) {
                            return false;
                        }
                        if (d2[board[x][y]] != -1 && d2[board[x][y]] != v) {
                            return false;
                        }
                        d1[v] = board[x][y];
                        d2[board[x][y]] = v;
                    }
                }
            }
            return true;
        };
        for (int i = 0; i < m - r + 1; ++i) {
            for (int j = 0; j < n - c + 1; ++j) {
                if (check(i, j)) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func findPattern(board [][]int, pattern []string) []int {
    m, n := len(board), len(board[0])
    r, c := len(pattern), len(pattern[0])
    check := func(i, j int) bool {
        d1 := [26]int{}
        d2 := [10]int{}
        for a := 0; a < r; a++ {
            for b := 0; b < c; b++ {
                x, y := i+a, j+b
                if pattern[a][b] >= '0' && pattern[a][b] <= '9' {
                    v := int(pattern[a][b] - '0')
                    if v != board[x][y] {
                        return false
                    }
                } else {
                    v := int(pattern[a][b] - 'a')
                    if d1[v] > 0 && d1[v]-1 != board[x][y] {
                        return false
                    }
                    if d2[board[x][y]] > 0 && d2[board[x][y]]-1 != v {
                        return false
                    }
                    d1[v] = board[x][y] + 1
                    d2[board[x][y]] = v + 1
                }
            }
        }
        return true
    }
    for i := 0; i < m-r+1; i++ {
        for j := 0; j < n-c+1; j++ {
            if check(i, j) {
                return []int{i, j}
            }
        }
    }
    return []int{-1, -1}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function findPattern(board: number[][], pattern: string[]): number[] {
    const m: number = board.length;
    const n: number = board[0].length;
    const r: number = pattern.length;
    const c: number = pattern[0].length;

    const check = (i: number, j: number): boolean => {
        const d1: number[] = Array(26).fill(-1);
        const d2: number[] = Array(10).fill(-1);

        for (let a = 0; a < r; ++a) {
            for (let b = 0; b < c; ++b) {
                const x: number = i + a;
                const y: number = j + b;

                if (!isNaN(Number(pattern[a][b]))) {
                    const v: number = Number(pattern[a][b]);
                    if (v !== board[x][y]) {
                        return false;
                    }
                } else {
                    const v: number = pattern[a].charCodeAt(b) - 'a'.charCodeAt(0);
                    if (d1[v] !== -1 && d1[v] !== board[x][y]) {
                        return false;
                    }
                    if (d2[board[x][y]] !== -1 && d2[board[x][y]] !== v) {
                        return false;
                    }
                    d1[v] = board[x][y];
                    d2[board[x][y]] = v;
                }
            }
        }
        return true;
    };

    for (let i = 0; i < m - r + 1; ++i) {
        for (let j = 0; j < n - c + 1; ++j) {
            if (check(i, j)) {
                return [i, j];
            }
        }
    }
    return [-1, -1];
}

Comments