Medium
Match Alphanumerical Pattern in Matrix I — C++
Full explanation · Time O(n * m * r * c) · Space O(1)
// Time: O(n * m * r * c)
// Space: O(1)
// brute force, hash table
class Solution {
public:
vector<int> findPattern(vector<vector<int>>& board, vector<string>& pattern) {
const auto& check = [&](int i, int j) {
vector<int> lookup(26, -1);
vector<bool> lookup2(10);
for (int r = 0; r < size(pattern); ++r) {
for (int c = 0; c < size(pattern[0]); ++c) {
const int y = board[i + r][j + c];
if (isdigit(pattern[r][c])) {
if (pattern[r][c] - '0' != y) {
return false;
}
continue;
}
const int x = pattern[r][c] - 'a';
if (lookup[x] == -1) {
if (lookup2[y]) {
return false;
}
lookup2[y] = true;
lookup[x] = y;
continue;
}
if (lookup[x] != y) {
return false;
}
}
}
return true;
};
for (int i = 0; i + size(pattern) - 1 < size(board); ++i) {
for (int j = 0; j + size(pattern[0]) - 1 < size(board[0]); ++j) {
if (check(i, j)) {
return {i, j};
}
}
}
return {-1, -1};
}
};