match-alphanumerical-pattern-in-matrix-i.cpp

// 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};
    }
};