3529. Count Cells in Overlapping Horizontal and Vertical Substrings
Medium
30 Points
Array
String
Rolling Hash
String Matching
Matrix
Hash Function
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:
Return the count of these cells.
Examples
Example 1
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: 1
Explanation:
The pattern "abaca" appears once as a horizontal substring (colored blue) and once as a vertical substring (colored red), intersecting at one cell (colored purple).
Example 2
Input: grid = [["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"
Output: 4
Explanation:
The cells colored above are all part of at least one horizontal and one vertical substring matching the pattern "aba" .
Example 3
Input: grid = [["a"]], pattern = "a"
Output: 1
Constraints
m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 105
1 <= pattern.length <= m * n
grid and pattern consist of only lowercase English letters.
3529. Count Cells in Overlapping Horizontal and Vertical Substrings
Medium
30 Points
Array
String
Rolling Hash
String Matching
Matrix
Hash Function
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:
Return the count of these cells.
Examples
Example 1
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: 1
Explanation:
The pattern "abaca" appears once as a horizontal substring (colored blue) and once as a vertical substring (colored red), intersecting at one cell (colored purple).
Example 2
Input: grid = [["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"
Output: 4
Explanation:
The cells colored above are all part of at least one horizontal and one vertical substring matching the pattern "aba" .
Example 3
Input: grid = [["a"]], pattern = "a"
Output: 1
Constraints
m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 105
1 <= pattern.length <= m * n
grid and pattern consist of only lowercase English letters.
Count Cells in Overlapping Horizontal and Vertical Substrings - Practice Coding | SlaveCode