mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-05 15:31:43 +08:00
59 lines
3.5 KiB
HTML
59 lines
3.5 KiB
HTML
<p>You are given an <code>m x n</code> matrix <code>grid</code> consisting of characters and a string <code>pattern</code>.</p>
|
|
|
|
<p>A <strong data-end="264" data-start="240">horizontal substring</strong> 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 <strong>not</strong> wrap from the bottom row back to the top.</p>
|
|
|
|
<p>A <strong data-end="484" data-start="462">vertical substring</strong> 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 <strong>not</strong> wrap from the last column back to the first.</p>
|
|
|
|
<p>Count the number of cells in the matrix that satisfy the following condition:</p>
|
|
|
|
<ul>
|
|
<li>The cell must be part of <strong>at least</strong> one horizontal substring and <strong>at least</strong> one vertical substring, where <strong>both</strong> substrings are equal to the given <code>pattern</code>.</li>
|
|
</ul>
|
|
|
|
<p>Return the count of these cells.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
<img alt="" src="https://assets.leetcode.com/uploads/2025/03/03/gridtwosubstringsdrawio.png" style="width: 150px; height: 187px;" />
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [["a","a","c","c"],["b","b","b","c"],["a","a","b","a"],["c","a","a","c"],["a","a","b","a"]], pattern = "abaca"</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">1</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>The pattern <code>"abaca"</code> appears once as a horizontal substring (colored blue) and once as a vertical substring (colored red), intersecting at one cell (colored purple).</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
<img alt="" src="https://assets.leetcode.com/uploads/2025/03/03/gridexample2fixeddrawio.png" style="width: 150px; height: 150px;" />
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">4</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>The cells colored above are all part of at least one horizontal and one vertical substring matching the pattern <code>"aba"</code>.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">grid = [["a"]], pattern = "a"</span></p>
|
|
|
|
<p><strong>Output:</strong> 1</p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>m == grid.length</code></li>
|
|
<li><code>n == grid[i].length</code></li>
|
|
<li><code>1 <= m, n <= 1000</code></li>
|
|
<li><code>1 <= m * n <= 10<sup>5</sup></code></li>
|
|
<li><code>1 <= pattern.length <= m * n</code></li>
|
|
<li><code>grid</code> and <code>pattern</code> consist of only lowercase English letters.</li>
|
|
</ul>
|