Leetcode 3529. Count Cells in Overlapping Horizontal and Vertical Substrings

• Leetcode 3529. Count Cells in Overlapping Horizontal and Vertical Substrings
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3529. Count Cells in Overlapping Horizontal and Vertical Substrings

1. 解题思路

这一题核心思路其实就是取出横向和纵向组成的两个长字符串，然后从中找出其中全部可以被pattern包括的位置，然后分别找出对应的节点的位置，最后将横向的结果和纵向的结果取一个交集即可。

这里，坐标的转换以及字符串的获取都是简单的，唯一的问题就在于如何在一个长字符串当中找出所有可以被pattern覆盖的位置，而这个就是一个典型的z算法的问题了，这里就不过多展开了，有兴趣的读者可以自行网上检索一下，我自己也写了一篇博客《经典算法：Z算法（z algorithm）》来作为备忘。

2. 代码实现

给出python代码实现如下：

def z_algorithm(s):n = len(s)z = [0 for _ in range(n)]l, r = -1, -1for i in range(1, n):if i > r:l, r = i, iwhile r < n and s[r-l] == s[r]:r += 1z[i] = r-lr -= 1else:k = i - lif z[k] < r - i + 1:z[i] = z[k]else:l = iwhile r < n and s[r-l] == s[r]:r += 1z[i] = r-lr -= 1z[0] = nreturn zclass Solution:def countCells(self, grid: List[List[str]], pattern: str) -> int:n, m = len(grid), len(grid[0])l = len(pattern)s1 = set()horizontal = "".join([grid[i][j] for i in range(n) for j in range(m)])z = z_algorithm(pattern + horizontal)[l:]valid = 0for i, c in enumerate(z):row, col = i // m, i % mif c >= l:valid = i + lif i < valid:s1.add((row, col))vertical = "".join([grid[i][j] for j in range(m) for i in range(n)])z = z_algorithm(pattern + vertical)[l:]valid = 0s2 = set()for i, c in enumerate(z):row, col = i % n, i // nif c >= l:valid = i + lif i < valid:s2.add((row, col))return len(s1 & s2)

提交代码评测得到：耗时699ms，占用内存64.3MB。