Skip to content

3078. Match Alphanumerical Pattern in Matrix I

  • Time: $O(|\texttt{board}||\texttt{board[0]}| \cdot |\texttt{pattern}||\texttt{pattern[0]}|)$
  • Space: $O(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
class Solution {
 public:
  vector<int> findPattern(vector<vector<int>>& board, vector<string>& pattern) {
    for (int x = 0; x < board.size() - pattern.size() + 1; ++x)
      for (int y = 0; y < board[0].size() - pattern[0].size() + 1; ++y)
        if (isMatch(board, x, y, pattern))
          return {x, y};
    return {-1, -1};
  }

 private:
  bool isMatch(const vector<vector<int>>& board, int x, int y,
               const vector<string>& pattern) {
    unordered_map<int, char> digitToLetter;
    unordered_map<char, int> letterToDigit;
    for (int i = 0; i < pattern.size(); ++i)
      for (int j = 0; j < pattern[i].size(); ++j) {
        const int digit = board[i + x][j + y];
        const char c = pattern[i][j];
        if (isdigit(c)) {
          if (c - '0' != digit)
            return false;
        } else {
          if (const auto it = digitToLetter.find(digit);
              it != digitToLetter.end() && it->second != c)
            return false;
          if (const auto it = letterToDigit.find(c);
              it != letterToDigit.end() && it->second != digit)
            return false;
          digitToLetter[digit] = c;
          letterToDigit[c] = digit;
        }
      }
    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
class Solution {
  public int[] findPattern(int[][] board, String[] pattern) {
    for (int x = 0; x < board.length - pattern.length + 1; ++x)
      for (int y = 0; y < board[0].length - pattern[0].length() + 1; ++y)
        if (isMatch(board, x, y, pattern))
          return new int[] {x, y};
    return new int[] {-1, -1};
  }

  private boolean isMatch(int[][] board, int x, int y, String[] pattern) {
    Map<Integer, Character> digitToLetter = new HashMap<>();
    Map<Character, Integer> letterToDigit = new HashMap<>();
    for (int i = 0; i < pattern.length; ++i)
      for (int j = 0; j < pattern[i].length(); ++j) {
        final int digit = board[i + x][j + y];
        final char c = pattern[i].charAt(j);
        if (Character.isDigit(c)) {
          if (c - '0' != digit)
            return false;
        } else {
          if (digitToLetter.getOrDefault(digit, c) != c)
            return false;
          if (letterToDigit.getOrDefault(c, digit) != digit)
            return false;
          digitToLetter.putIfAbsent(digit, c);
          letterToDigit.putIfAbsent(c, digit);
        }
      }
    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
class Solution:
  def findPattern(
      self,
      board: list[list[int]],
      pattern: list[str],
  ) -> list[int]:
    def isMatch(x: int, y: int) -> bool:
      digitToLetter = {}
      letterToDigit = {}
      for i, row in enumerate(pattern):
        for j, c in enumerate(row):
          digit = board[i + x][j + y]
          if c.isdigit():
            if int(c) != digit:
              return False
          else:
            if digitToLetter.get(digit, c) != c:
              return False
            if letterToDigit.get(c, digit) != digit:
              return False
            digitToLetter[digit] = c
            letterToDigit[c] = digit
      return True

    for x in range(len(board) - len(pattern) + 1):
      for y in range(len(board[0]) - len(pattern[0]) + 1):
        if isMatch(x, y):
          return [x, y]

    return [-1, -1]