Count Cells in Overlapping Horizontal and Vertical Substrings
You are given an m x n matrix grid consisting of characters and a string pattern.
A horizontal substring is a contiguous sequence of characters read from left to right. If the end of a row is reached before the substring is complete, it wraps to the first column of the next row and continues as needed. You do not wrap from the bottom row back to the top.
A vertical substring is a contiguous sequence of characters read from top to bottom. If the bottom of a column is reached before the substring is complete, it wraps to the first row of the next column and continues as needed. You do not wrap from the last column back to the first.
Count the number of cells in the matrix that satisfy the following condition:
- The cell must be part of at least one horizontal substring and at least one vertical substring, where both substrings are equal to the given
pattern.
Return the count of these cells.
Example 1
a a c c b b b c a a b a c a a c a a b a
Input
grid = [["a","a","c","c"],["b","b","b","c"],["a","a","b","a"],["c","a","a","c"],["a","a","b","a"]], pattern = "abaca"Output
1The pattern
"abaca" appears once as a horizontal substring and once as a vertical substring, intersecting at one cell.Example 2
c a a a a a b a b b a a a a b a
Input
grid = [["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"Output
4The counted cells are all part of at least one horizontal and one vertical substring matching the pattern
"aba".Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 1000
- 1 <= m * n <= 10^5
- 1 <= pattern.length <= m * n
- grid and pattern consist of only lowercase English letters.