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 matchespattern.
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 length2containing the row number and column number of the upper-left corner of a submatrix ofboardwhich 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].
1|2|2---|---|---2|2|32|3|3a | 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|46|6|6a | b
---|---6|6Input: 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|1x | 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.
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.
classSolution {
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;
} elseif (d2l.count(v)) {
if (d2l[v] != c) ok = false;
} else {
l2d[c] = v;
d2l[v] = c;
}
}
}
}
if (ok) return {i, j};
}
}
return {-1, -1};
}
};
classSolution {
publicint[]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;
} elseif (d2l.containsKey(v)) {
if (d2l.get(v) != c) ok =false;
} else {
l2d.put(c, v);
d2l.put(v, c);
}
}
}
}
if (ok) returnnewint[]{i, j};
}
}
returnnewint[]{-1, -1};
}
}
classSolution {
funfindPattern(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 in0..m-p) {
for (j in0..n-q) {
val l2d = mutableMapOf<Char, Int>()
val d2l = mutableMapOf<Int, Char>()
var ok = truefor (x in0 until p) {
for (y in0 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 } elseif (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)
}
}
classSolution:
deffindPattern(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 =Truefor 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 =Falseelse:
if c in l2d:
if l2d[c] != v:
ok =Falseelif v in d2l:
if d2l[v] != c:
ok =Falseelse:
l2d[c] = v
d2l[v] = c
ifnot ok:
breakifnot ok:
breakif ok:
return [i, j]
return [-1, -1]
impl Solution {
pubfnfind_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 in0..=m-p {
for j in0..=n-q {
letmut l2d = std::collections::HashMap::new();
letmut d2l = std::collections::HashMap::new();
letmut ok =true;
'outer: for x in0..p {
for y in0..q {
let c = pattern[x][y];
let v = board[i+x][j+y];
if c.is_ascii_digit() {
if v != (c asu8-b'0') asi32 {
ok =false;
break 'outer;
}
} else {
iflet Some(&d) = l2d.get(&c) {
if d != v {
ok =false;
break 'outer;
}
} elseiflet Some(&l) = d2l.get(&v) {
if l != c {
ok =false;
break 'outer;
}
} else {
l2d.insert(c, v);
d2l.insert(v, c);
}
}
}
}
if ok {
returnvec![i asi32, j asi32];
}
}
}
vec![-1, -1]
}
}