Description
Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of submatrices that contain:
grid[0][0]- an equal frequency of
'X'and'Y'. - at least one
'X'.
Example 1:
Input: grid = [["X","Y","."],["Y",".","."]]
Output: 3
Explanation:
Example 2:
Input: grid = [["X","X"],["X","Y"]]
Output: 0
Explanation:
No submatrix has an equal frequency of 'X' and 'Y'.
Example 3:
Input: grid = [[".","."],[".","."]]
Output: 0
Explanation:
No submatrix has at least one 'X'.
Constraints:
1 <= grid.length, grid[i].length <= 1000grid[i][j]is either'X','Y', or'.'.
Solution
Python3
class Solution:
def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
X = [[0] * (cols + 1) for _ in range(rows + 1)]
Y = [[0] * (cols + 1) for _ in range(rows + 1)]
res = 0
for i in range(1, rows + 1):
for j in range(1, cols + 1):
X[i][j] = int(grid[i - 1][j - 1] == "X") + X[i - 1][j] + X[i][j - 1] - X[i - 1][j - 1]
Y[i][j] = int(grid[i - 1][j - 1] == "Y") + Y[i - 1][j] + Y[i][j - 1] - Y[i - 1][j - 1]
if X[i][j] > 0 and X[i][j] == Y[i][j]:
res += 1
return res