题目描述
给定一个二维整数矩阵 board 和一个二维字符矩阵 pattern。其中 0 <= board[r][c] <= 9 并且 pattern 的每个元素是一个数字或一个小写英文字母。
你的任务是找到 匹配 board 的子矩阵 pattern。
如果我们能用一些数字（每个 不同 的字母对应 不同 的数字）替换 pattern 中包含的字母使得结果矩阵与整数矩阵 part 相同，我们称整数矩阵 part 与 pattern 匹配。换句话说，
- 这两个矩阵具有相同的维数。
- 如果
pattern[r][c] 是一个数字，那么 part[r][c] 必须是 相同的 数字。 - 如果
pattern[r][c] 是一个字母 x： - 对于每个
pattern[i][j] == x，part[i][j] 一定与 part[r][c] 相同。 - 对于每个
pattern[i][j] != x，part[i][j] 一定与 part[r][c] 不同。
返回一个长度为 2 的数组，包含匹配 pattern 的 board 的子矩阵左上角的行号和列号。如果有多个这样的子矩阵，返回行号更小的子矩阵。如果依然有多个，则返回列号更小的子矩阵。如果没有符合的答案，返回 [-1, -1]。
示例 1：
输入：board = [[1,2,2],[2,2,3],[2,3,3]], pattern = ["ab","bb"]
输出：[0,0]
解释：如果我们考虑这个映射："a" -> 1 并且 "b" -> 2；左上角为 (0,0) 的子矩阵与上面的矩阵中加粗的相匹配。
注意左上角为 (1,1) 的子矩阵同样匹配，但它在另一个之后出现，所以我们返回 [0,0]。
示例 2：
输入：board = [[1,1,2],[3,3,4],[6,6,6]], pattern = ["ab","66"]
输出：[1,1]
解释：如果我们考虑这个映射："a" -> 3 并且 "b" -> 4；左上角为 (1,1) 的子矩阵与上面的矩阵中加粗的匹配。
注意 "a" 和 "b" 对应的值必须不同，左上角为 (1,0) 的子矩阵不匹配。因此，我们返回 [1,1]。
示例 3：
输入：board = [[1,2],[2,1]], pattern = ["xx"]
输出：[-1,-1]
解释： 由于匹配子矩阵的值必须相同，因此不存在匹配。因此，我们返回 [-1,-1]。
提示：
1 <= board.length <= 501 <= board[i].length <= 500 <= board[i][j] <= 91 <= pattern.length <= 501 <= pattern[i].length <= 50pattern[i][j] 表示为一个数字的字符串或一个小写英文字母。
解法
方法一：枚举
思考
模式中的字母表示未知数字且须双向一致，数字则须相等。棋盘与模式都不超过 \(50\)，枚举对齐位置可行。
每个左上角用两张映射表检查字母与数字的一一对应，遇数字格直接比较。
按行优先枚举 \((i,j)\)，第一次匹配成功即返回。
我们不妨记 \(m\) 和 \(n\) 分别为矩阵 board 的行数和列数，记 \(r\) 和 \(c\) 分别为矩阵 pattern 的行数和列数。
我们可以从小到大枚举矩阵 board 中的每一个可能的子矩阵的左上角位置 \((i, j)\)，然后判断以 \((i, j)\) 为左上角的 \(r \times c\) 的子矩阵是否与 pattern 匹配。如果找到了一个匹配的子矩阵，我们就返回 \((i, j)\)。否则，我们返回 \((-1, -1)\)。
时间复杂度 \(O(m \times n \times r \times c)\)，其中 \(m\) 和 \(n\) 分别是矩阵 board 的行数和列数，而 \(r\) 和 \(c\) 分别是矩阵 pattern 的行数和列数。空间复杂度 \(O(|\Sigma|)\)，其中 \(\Sigma\) 是字符集，本题中 \(\Sigma\) 包括数字和小写字母，因此 \(|\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];
}
|