Question

3078. 矩阵中的字母数字模式匹配 I

English Version

题目描述

给定一个二维整数矩阵 board 和一个二维字符矩阵 pattern。其中 0 <= board[r][c] <= 9 并且 pattern 的每个元素是一个数字或一个小写英文字母。

你的任务是找到 匹配 board 的子矩阵 pattern。

如果我们能用一些数字（每个 不同 的字母对应 不同 的数字）替换 pattern 中包含的字母使得结果矩阵与整数矩阵 part 相同，我们称整数矩阵 part 与 pattern 匹配。换句话说，

• 矩阵具有相同的维数。
• 如果 pattern[r][c] 是一个数字，那么 part[r][c] 一定 也 是数字。
• 如果 pattern[r][c] 是一个字母 x：
  • 对于每个 pattern[i][j] == x，part[i][j] 一定与 part[r][c] 相同。
  • 对于每个 pattern[i][j] != x，part[i][j] 一定与 part[r][c] 不同。

返回一个长度为_ _2 的数组，包含匹配 pattern 的 board 的子矩阵左上角的行号和列号。如果有一个以上这样的子矩阵，返回行号更小的子矩阵。如果依然相同，则返回列号更小的子矩阵。如果没有符合的答案，返回 [-1, -1]。

 

示例 1：

1	2	2
2	2	3
2	3	3

a	b
b	b

输入：board = [[1,2,2],[2,2,3],[2,3,3]], pattern = ["ab","bb"]

输出：[0,0]

解释：如果我们考虑这个映射："a" -> 1 并且 "b" -> 2；左上角为 (0,0) 的子矩阵与上面的矩阵中加粗的相匹配。

注意左上角为 (1,1) 的子矩阵同样匹配，但它在另一个之后出现，所以我们返回 [0,0]。

示例 2：

1	1	2
3	3	4
6	6	6

a	b
6	6

输入：board = [[1,1,2],[3,3,4],[6,6,6]], pattern = ["ab","66"]

输出：[1,1]

解释：如果我们考虑这个映射："a" -> 3 并且 "b" -> 4；左上角为 (1,1) 的子矩阵与上面的矩阵中加粗的匹配。

注意 "a" 和 "b" 对应的值必须不同，左上角为 (1,0) 的子矩阵不匹配。因此，我们返回 [1,1]。

示例 3：

1	2
2	1

x

x

输入：board = [[1,2],[2,1]], pattern = ["xx"]

输出：[-1,-1]

解释： 由于匹配子矩阵的值必须相同，因此不存在匹配。因此，我们返回 [-1,-1]。

 

提示：

• 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] 表示为一个数字的字符串或一个小写英文字母。

解法

方法一：枚举

我们不妨记 $m$ 和 $n$ 分别为矩阵 board 的行数和列数，记 $r$ 和 $c$ 分别为矩阵 pattern 的行数和列数。

我们可以从小到大枚举矩阵 board 中的每一个可能的子矩阵的左上角位置 $(i, j)$，然后判断以 $(i, j)$ 为左上角的 $r \times c$ 的子矩阵是否与 pattern 匹配。如果找到了一个匹配的子矩阵，我们就返回 $(i, j)$。否则，我们返回 $(-1, -1)$。

时间复杂度 $O(m \times n \times r \times c)$，其中 $m$ 和 $n$ 分别是矩阵 board 的行数和列数，而 $r$ 和 $c$ 分别是矩阵 pattern 的行数和列数。空间复杂度 $O(|\Sigma|)$，其中 $\Sigma$ 是字符集，本题中 $\Sigma$ 包括数字和小写字母，因此 $|\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];
}