题目描述
给你一个二维字符矩阵 grid
,其中 grid[i][j]
可能是 'X'
、'Y'
或 '.'
,返回满足以下条件的子矩阵数量:
- 包含
grid[0][0]
'X'
和'Y'
的频数相等。- 至少包含一个
'X'
。
样例
输入: grid = [["X","Y","."],["Y",".","."]]
输出: 3
解释:
输入: grid = [["X","X"],["X","Y"]]
输出: 0
解释:
不存在满足 'X' 和 'Y' 频数相等的子矩阵。
输入: grid = [[".","."],[".","."]]
输出: 0
解释:
不存在满足至少包含一个 'X' 的子矩阵。
限制
1 <= grid.length, grid[i].length <= 1000
grid[i][j]
可能是'X'
、'Y'
或'.'
。
算法
(二维前缀和) $O(mn)$
- 使用两个数组分别计算
X
和Y
出现次数的二维前缀和。如果前缀和相同且大于 0,则累加答案。
时间复杂度
- 遍历二维数组一次,故时间复杂度为 $O(mn)$。
空间复杂度
- 需要 $O(mn)$ 的额外空间存储二维前缀和。
C++ 代码
class Solution {
public:
int numberOfSubmatrices(vector<vector<char>>& grid) {
const int m = grid.size(), n = grid[0].size();
vector<vector<int>> x(m, vector<int>(n, 0));
vector<vector<int>> y(m, vector<int>(n, 0));
int ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (i > 0) {
x[i][j] = x[i][j] + x[i - 1][j];
y[i][j] = y[i][j] + y[i - 1][j];
}
if (j > 0) {
x[i][j] = x[i][j] + x[i][j - 1];
y[i][j] = y[i][j] + y[i][j - 1];
}
if (i > 0 && j > 0) {
x[i][j] = x[i][j] - x[i - 1][j - 1];
y[i][j] = y[i][j] - y[i - 1][j - 1];
}
if (grid[i][j] == 'X') ++x[i][j];
else if (grid[i][j] == 'Y') ++y[i][j];
if (x[i][j] > 0 && x[i][j] == y[i][j])
++ans;
}
return ans;
}
};