What is the key pattern in Count Cells in Overlapping Horizontal and Vertical Substrings?

The key pattern is finding cells that are part of both horizontal and vertical occurrences of the given string pattern in the grid.

Can rolling hash handle both horizontal and vertical substrings?

Yes, rolling hash can be applied row-wise and column-wise to efficiently detect all substring matches.

How do I handle wrapping across rows or columns?

Concatenate the next row or column as needed when the substring extends past the end, ensuring you do not wrap back to the first row or column.

What is the time complexity for large grids?

Using rolling hash, scanning all rows and columns is typically O(m*n), which handles the constraints efficiently.

How can I avoid double counting cells?

Store horizontal and vertical match coordinates in separate sets and count only the cells present in both sets.

#3529

Medium

auto_awesome数组·string

LeetCode 题解工作台

统计水平子串和垂直子串重叠格子的数目

给你一个由字符组成的 m x n 矩阵 grid 和一个字符串 pattern 。水平子串是从左到右的一段连续字符序列。如果子串到达了某行的末尾，它将换行并从下一行的第一个字符继续。不会从最后一行回到第一行。垂直子串是从上到下的一段连续字符序列。如果子串到达了某列的底部，它将换列并从下一…

数组字符串滚动哈希字符串匹配矩阵

题目描述

给你一个由字符组成的 m x n 矩阵 grid 和一个字符串 pattern。

水平子串 是从左到右的一段连续字符序列。如果子串到达了某行的末尾，它将换行并从下一行的第一个字符继续。不会从最后一行回到第一行。

垂直子串 是从上到下的一段连续字符序列。如果子串到达了某列的底部，它将换列并从下一列的第一个字符继续。不会从最后一列回到第一列。

请统计矩阵中满足以下条件的单元格数量：

该单元格必须属于至少一个等于 pattern 的水平子串，且属于至少一个等于 pattern 的垂直子串。

返回满足条件的单元格数量。

示例 1：

输入： grid = [["a","a","c","c"],["b","b","b","c"],["a","a","b","a"],["c","a","a","c"],["a","a","b","a"]], pattern = "abaca"

输出： 1

解释：

"abaca" 作为一个水平子串（蓝色）和一个垂直子串（红色）各出现一次，并在一个单元格（紫色）处相交。

示例 2：

输入： grid = [["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"

输出： 4

解释：

上述被标记的单元格都同时属于至少一个 "aba" 的水平和垂直子串。

示例 3：

输入： grid = [["a"]], pattern = "a"

输出： 1

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
1 <= pattern.length <= m * n
grid 和 pattern 仅由小写英文字母组成。

lightbulb

解题思路

方法一

1

2

speed

复杂度分析

指标	值
时间	complexity depends on the rolling hash implementation, typically O(m _n) for scanning all rows and columns. Space complexity is O(m_ n) to store match coordinates for horizontal and vertical occurrences.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you considering pattern matching optimization for large grids?
question_mark
Can you handle wrapping logic in both horizontal and vertical directions efficiently?
question_mark
How will you track overlapping cells without redundant computation?

warning

常见陷阱

外企场景

error
Forgetting to wrap rows or columns correctly when scanning substrings.
error
Counting a cell multiple times if it appears in multiple matches in one orientation.
error
Ignoring edge cases when pattern length exceeds row or column segments.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count cells for multiple patterns simultaneously using the same rolling hash approach.
arrow_right_alt
Modify the grid to allow toroidal wrapping and count overlapping cells under new rules.
arrow_right_alt
Count overlapping cells only for non-overlapping horizontal and vertical substrings.

help

常见问题

外企场景

继续练习

#3292 形成目标字符串需要的最少字符串数 II #3291 形成目标字符串需要的最少字符串数 I #3045 统计前后缀下标对 II