Question

3078. Match Alphanumerical Pattern in Matrix I

中文文档

Description

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, then part[r][c] must be the same digit.
• If pattern[r][c] is a letter x:
  • For every pattern[i][j] == x, part[i][j] must be the same as part[r][c].
  • For every pattern[i][j] != x, part[i][j] must be different than part[r][c].

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 <= 50
• 1 <= board[i].length <= 50
• 0 <= board[i][j] <= 9
• 1 <= pattern.length <= 50
• 1 <= pattern[i].length <= 50
• pattern[i][j] is either a digit represented as a string or a lowercase English letter.

Solutions

Solution 1: Enumeration

Let's denote $m$ and $n$ as the number of rows and columns in the matrix board, and $r$ and $c$ as the number of rows and columns in the matrix pattern.

We can enumerate each possible sub-matrix's top-left position $(i, j)$ in the board from small to large, and then determine whether the $r \times c$ sub-matrix with $(i, j)$ as the top-left corner matches pattern. If we find a matching sub-matrix, we return $(i, j)$. Otherwise, we return $(-1, -1)$.

The time complexity is $O(m \times n \times r \times c)$, where $m$ and $n$ are the number of rows and columns in the matrix board, and $r$ and $c$ are the number of rows and columns in the matrix pattern. The space complexity is $O(|\Sigma|)$, where $\Sigma$ is the character set. In this problem, $\Sigma$ includes numbers and lowercase letters, so $|\Sigma| \leq 36$.

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