| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
Medium |
|
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, thenpart[r][c]must be the same digit. - If
pattern[r][c]is a letterx:- For every
pattern[i][j] == x,part[i][j]must be the same aspart[r][c]. - For every
pattern[i][j] != x,part[i][j]must be different thanpart[r][c].
- For every
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 <= 501 <= board[i].length <= 500 <= board[i][j] <= 91 <= pattern.length <= 501 <= pattern[i].length <= 50pattern[i][j]is either a digit represented as a string or a lowercase English letter.
Let's denote board, and pattern.
We can enumerate each possible sub-matrix's top-left position board from small to large, and then determine whether the pattern. If we find a matching sub-matrix, we return
The time complexity is board, and pattern. The space complexity is
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]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;
}
}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};
}
};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}
}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];
}