Problem

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 length2 containing the row number and column number of the upper-left corner of a submatrix ofboard which matchespattern . 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].

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
3
4
5
6
7
8
9
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.

Solution

Method 1 – Backtracking with Hash Maps

Intuition

We need to check every possible submatrix of the board that matches the pattern. For each submatrix, we try to assign digits to letters in the pattern such that all constraints are satisfied. We use hash maps to track letter-to-digit and digit-to-letter assignments.

Approach

  1. For each possible top-left position (i, j) in board, extract a submatrix of the same size as pattern.
  2. For each submatrix, use two hash maps:
    • One for mapping letters to digits.
    • One for mapping digits to letters.
  3. For each cell in the pattern:
    • If it’s a digit, check if it matches the board cell.
    • If it’s a letter, check or assign a mapping, ensuring consistency and uniqueness.
  4. If all cells match, return the coordinates (i, j).
  5. If no match is found, return [-1, -1].

Code

 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
class Solution {
public:
    vector<int> findPattern(vector<vector<int>>& board, vector<vector<char>>& pattern) {
        int m = board.size(), n = board[0].size();
        int p = pattern.size(), q = pattern[0].size();
        for (int i = 0; i + p <= m; ++i) {
            for (int j = 0; j + q <= n; ++j) {
                unordered_map<char, int> l2d;
                unordered_map<int, char> d2l;
                bool ok = true;
                for (int x = 0; x < p && ok; ++x) {
                    for (int y = 0; y < q && ok; ++y) {
                        char c = pattern[x][y];
                        int v = board[i+x][j+y];
                        if (isdigit(c)) {
                            if (v != c - '0') ok = false;
                        } else {
                            if (l2d.count(c)) {
                                if (l2d[c] != v) ok = false;
                            } else if (d2l.count(v)) {
                                if (d2l[v] != c) ok = false;
                            } else {
                                l2d[c] = v;
                                d2l[v] = c;
                            }
                        }
                    }
                }
                if (ok) 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
func findPattern(board [][]int, pattern [][]byte) []int {
    m, n := len(board), len(board[0])
    p, q := len(pattern), len(pattern[0])
    for i := 0; i+p <= m; i++ {
        for j := 0; j+q <= n; j++ {
            l2d := map[byte]int{}
            d2l := map[int]byte{}
            ok := true
            for x := 0; x < p && ok; x++ {
                for y := 0; y < q && ok; y++ {
                    c := pattern[x][y]
                    v := board[i+x][j+y]
                    if c >= '0' && c <= '9' {
                        if v != int(c-'0') {
                            ok = false
                        }
                    } else {
                        if vv, f := l2d[c]; f {
                            if vv != v {
                                ok = false
                            }
                        } else if cc, f := d2l[v]; f {
                            if cc != c {
                                ok = false
                            }
                        } else {
                            l2d[c] = v
                            d2l[v] = c
                        }
                    }
                }
            }
            if ok {
                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
class Solution {
    public int[] findPattern(int[][] board, char[][] pattern) {
        int m = board.length, n = board[0].length;
        int p = pattern.length, q = pattern[0].length;
        for (int i = 0; i + p <= m; i++) {
            for (int j = 0; j + q <= n; j++) {
                Map<Character, Integer> l2d = new HashMap<>();
                Map<Integer, Character> d2l = new HashMap<>();
                boolean ok = true;
                for (int x = 0; x < p && ok; x++) {
                    for (int y = 0; y < q && ok; y++) {
                        char c = pattern[x][y];
                        int v = board[i+x][j+y];
                        if (Character.isDigit(c)) {
                            if (v != c - '0') ok = false;
                        } else {
                            if (l2d.containsKey(c)) {
                                if (l2d.get(c) != v) ok = false;
                            } else if (d2l.containsKey(v)) {
                                if (d2l.get(v) != c) ok = false;
                            } else {
                                l2d.put(c, v);
                                d2l.put(v, c);
                            }
                        }
                    }
                }
                if (ok) return new int[]{i, j};
            }
        }
        return new 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
class Solution {
    fun findPattern(board: Array<IntArray>, pattern: Array<CharArray>): IntArray {
        val m = board.size
        val n = board[0].size
        val p = pattern.size
        val q = pattern[0].size
        for (i in 0..m-p) {
            for (j in 0..n-q) {
                val l2d = mutableMapOf<Char, Int>()
                val d2l = mutableMapOf<Int, Char>()
                var ok = true
                for (x in 0 until p) {
                    for (y in 0 until q) {
                        val c = pattern[x][y]
                        val v = board[i+x][j+y]
                        if (c.isDigit()) {
                            if (v != c - '0') ok = false
                        } else {
                            if (l2d.containsKey(c)) {
                                if (l2d[c] != v) ok = false
                            } else if (d2l.containsKey(v)) {
                                if (d2l[v] != c) ok = false
                            } else {
                                l2d[c] = v
                                d2l[v] = c
                            }
                        }
                        if (!ok) break
                    }
                    if (!ok) break
                }
                if (ok) return intArrayOf(i, j)
            }
        }
        return intArrayOf(-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
class Solution:
    def findPattern(self, board: list[list[int]], pattern: list[list[str]]) -> list[int]:
        m, n = len(board), len(board[0])
        p, q = len(pattern), len(pattern[0])
        for i in range(m - p + 1):
            for j in range(n - q + 1):
                l2d: dict[str, int] = {}
                d2l: dict[int, str] = {}
                ok = True
                for x in range(p):
                    for y in range(q):
                        c = pattern[x][y]
                        v = board[i+x][j+y]
                        if c.isdigit():
                            if v != int(c):
                                ok = False
                        else:
                            if c in l2d:
                                if l2d[c] != v:
                                    ok = False
                            elif v in d2l:
                                if d2l[v] != c:
                                    ok = False
                            else:
                                l2d[c] = v
                                d2l[v] = c
                        if not ok:
                            break
                    if not ok:
                        break
                if ok:
                    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
44
45
46
impl Solution {
    pub fn find_pattern(board: Vec<Vec<i32>>, pattern: Vec<Vec<char>>) -> Vec<i32> {
        let m = board.len();
        let n = board[0].len();
        let p = pattern.len();
        let q = pattern[0].len();
        for i in 0..=m-p {
            for j in 0..=n-q {
                let mut l2d = std::collections::HashMap::new();
                let mut d2l = std::collections::HashMap::new();
                let mut ok = true;
                'outer: for x in 0..p {
                    for y in 0..q {
                        let c = pattern[x][y];
                        let v = board[i+x][j+y];
                        if c.is_ascii_digit() {
                            if v != (c as u8 - b'0') as i32 {
                                ok = false;
                                break 'outer;
                            }
                        } else {
                            if let Some(&d) = l2d.get(&c) {
                                if d != v {
                                    ok = false;
                                    break 'outer;
                                }
                            } else if let Some(&l) = d2l.get(&v) {
                                if l != c {
                                    ok = false;
                                    break 'outer;
                                }
                            } else {
                                l2d.insert(c, v);
                                d2l.insert(v, c);
                            }
                        }
                    }
                }
                if ok {
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![-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
class Solution {
    findPattern(board: number[][], pattern: string[][]): number[] {
        const m = board.length, n = board[0].length;
        const p = pattern.length, q = pattern[0].length;
        for (let i = 0; i + p <= m; i++) {
            for (let j = 0; j + q <= n; j++) {
                const l2d = new Map<string, number>();
                const d2l = new Map<number, string>();
                let ok = true;
                for (let x = 0; x < p && ok; x++) {
                    for (let y = 0; y < q && ok; y++) {
                        const c = pattern[x][y];
                        const v = board[i+x][j+y];
                        if (c >= '0' && c <= '9') {
                            if (v !== +c) ok = false;
                        } else {
                            if (l2d.has(c)) {
                                if (l2d.get(c) !== v) ok = false;
                            } else if (d2l.has(v)) {
                                if (d2l.get(v) !== c) ok = false;
                            } else {
                                l2d.set(c, v);
                                d2l.set(v, c);
                            }
                        }
                    }
                }
                if (ok) return [i, j];
            }
        }
        return [-1, -1];
    }
}

Complexity

  • ⏰ Time complexity: O((m*n*p*q)), where m, n are the board dimensions and p, q are the pattern dimensions, as we check every submatrix and every cell.
  • 🧺 Space complexity: O(p*q), for the hash maps used in each check.