Medium

题目描述

给定一个 m x n 的字符矩阵 grid 和一个字符串 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
解释：pattern "abaca" 作为水平子串出现一次（蓝色），作为垂直子串出现一次（红色），在一个单元格处相交（紫色）。

示例 2：

输入：grid = [["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"
输出：4
解释：上面着色的单元格都是至少一个水平和一个垂直子串匹配 pattern "aba" 的一部分。

示例 3：

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

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 10^5
  • 1 <= pattern.length <= m * n
  • grid 和 pattern 只包含小写英文字母

解题思路

这道题需要找出矩阵中同时属于水平子串匹配和垂直子串匹配的单元格。

解题思路

  1. 理解题意：

    • 水平子串：从左到右读取，行尾换到下一行开头
    • 垂直子串：从上到下读取，列尾换到下一列开头
    • 需要找到同时满足两种匹配的单元格

  2. 算法步骤：

    • 首先将二维矩阵按照水平和垂直方向分别转换为一维字符串
    • 使用字符串匹配算法（如 KMP）找到所有匹配位置
    • 将一维位置转换回二维坐标
    • 使用集合记录水平和垂直匹配涉及的单元格
    • 计算两个集合的交集

  3. 关键点：

    • 水平方向：位置 pos 对应坐标 (pos / n, pos % n)
    • 垂直方向：位置 pos 对应坐标 (pos % m, pos / m)
    • 每个匹配的起始位置需要标记整个 pattern 长度范围内的所有单元格

  4. 优化：

    • 使用 KMP 算法进行高效的字符串匹配
    • 使用哈希集合快速计算交集

代码实现

class Solution {
private:
    vector<int> computeLPS(const string& pattern) {
        int m = pattern.length();
        vector<int> lps(m, 0);
        int len = 0;
        int i = 1;
        
        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
    
    vector<int> KMPSearch(const string& text, const string& pattern) {
        vector<int> matches;
        int n = text.length();
        int m = pattern.length();
        
        if (m > n) return matches;
        
        vector<int> lps = computeLPS(pattern);
        int i = 0, j = 0;
        
        while (i < n) {
            if (text[i] == pattern[j]) {
                i++;
                j++;
            }
            
            if (j == m) {
                matches.push_back(i - j);
                j = lps[j - 1];
            } else if (i < n && text[i] != pattern[j]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return matches;
    }
    
public:
    int countCells(vector<vector<char>>& grid, string pattern) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 构建水平字符串
        string horizontal = "";
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                horizontal += grid[i][j];
            }
        }
        
        // 构建垂直字符串
        string vertical = "";
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                vertical += grid[i][j];
            }
        }
        
        // 找到所有匹配
        vector<int> hMatches = KMPSearch(horizontal, pattern);
        vector<int> vMatches = KMPSearch(vertical, pattern);
        
        // 记录匹配涉及的单元格
        set<pair<int, int>> hCells, vCells;
        
        for (int pos : hMatches) {
            for (int k = 0; k < pattern.length(); k++) {
                int idx = pos + k;
                int r = idx / n;
                int c = idx % n;
                hCells.insert({r, c});
            }
        }
        
        for (int pos : vMatches) {
            for (int k = 0; k < pattern.length(); k++) {
                int idx = pos + k;
                int r = idx % m;
                int c = idx / m;
                vCells.insert({r, c});
            }
        }
        
        // 计算交集
        int count = 0;
        for (const auto& cell : hCells) {
            if (vCells.count(cell)) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def computeLPS(self, pattern):
        m = len(pattern)
        lps = [0] * m
        length = 0
        i = 1
        
        while i < m:
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps
    
    def KMPSearch(self, text, pattern):
        matches = []
        n = len(text)
        m = len(pattern)
        
        if m > n:
            return matches
        
        lps = self.computeLPS(pattern)
        i = j = 0
        
        while i < n:
            if text[i] == pattern[j]:
                i += 1
                j += 1
            
            if j == m:
                matches.append(i - j)
                j = lps[j - 1]
            elif i < n and text[i] != pattern[j]:
                if j != 0:
                    j = lps[j - 1]
                else:
                    i += 1
        
        return matches
    
    def countCells(self, grid: List[List[str]], pattern: str) -> int:
        m, n = len(grid), len(grid[0])
        
        # 构建水平字符串
        horizontal = ""
        for i in range(m):
            for j in range(n):
                horizontal += grid[i][j]
        
        # 构建垂直字符串
        vertical = ""
        for j in range(n):
            for i in range(m):
                vertical += grid[i][j]
        
        # 找到所有匹配
        h_matches = self.KMPSearch(horizontal, pattern)
        v_matches = self.KMPSearch(vertical, pattern)
        
        # 记录匹配涉及的单元格
        h_cells = set()
        v_cells = set()
        
        for pos in h_matches:
            for k in range(len(pattern)):
                idx = pos + k
                r = idx // n
                c = idx % n
                h_cells.add((r, c))
        
        for pos in v_matches:
            for k in range(len(pattern)):
                idx = pos + k
                r = idx % m
                c = idx // m
                v_cells.add((r, c))
        
        # 计算交集
        return len(h_cells & v_cells)

public class Solution {
    private int[] ComputeLPS(string pattern) {
        int m = pattern.Length;
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        
        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
    
    private List<int> KMPSearch(string text, string pattern) {
        List<int> matches = new List<int>();
        int n = text.Length;
        int m = pattern.Length;
        
        if (m > n) return matches;
        
        int[] lps = ComputeLPS(pattern);
        int i = 0, j = 0;
        
        while (i < n) {
            if (text[i] == pattern[j]) {
                i++;
                j++;
            }
            
            if (j == m) {
                matches.Add(i - j);
                j = lps[j - 1];
            } else if (i < n && text[i] != pattern[j]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return matches;
    }
    
    public int CountCells(char[][] grid, string pattern) {
        int m = grid.Length;
        int n = grid[0].Length;
        
        // 构建水平字符串
        StringBuilder horizontal = new StringBuilder();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                horizontal.Append(grid[i][j]);
            }
        }
        
        // 构建垂直字符串
        StringBuilder vertical = new StringBuilder();
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                vertical.Append(grid[i][j]);
            }
        }
        
        // 找到所有匹配
        List<int> hMatches = KMPSearch(horizontal.ToString(), pattern);
        List<int> vMatches = KMPSearch(vertical.ToString(), pattern);
        
        // 记录匹配涉及的单元格
        HashSet<(int, int)> hCells = new HashSet<(int, int)>();
        HashSet<(int, int)> vCells = new HashSet<(int, int)>();
        
        foreach (int pos in hMatches) {
            for (int k = 0; k < pattern.Length; k++) {
                int idx = pos + k;
                int r = idx / n;
                int c = idx % n;
                hCells.Add((r, c));
            }
        }
        
        foreach (int pos in vMatches) {
            for (int k = 0; k < pattern.Length; k++) {
                int idx = pos + k;
                int r = idx % m;
                int c = idx / m;
                vCells.Add((r, c));
            }
        }
        
        // 计算交集
        int count = 0;
        foreach (var cell in hCells) {
            if (vCells.Contains(cell)) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {character[][]} grid
 * @param {string} pattern
 * @return {number}
 */
var countCells = function(grid, pattern) {
    const m = grid.length;
    const n = grid[0].length;
    const patternLen = pattern.length;
    
    const horizontalCells = new Set();
    const verticalCells = new Set();
    
    // Find horizontal substrings
    for (let i = 0; i < m * n - patternLen + 1; i++) {
        let match = true;
        for (let j = 0; j < patternLen; j++) {
            const pos = i + j;
            const row = Math.floor(pos / n);
            const col = pos % n;
            if (grid[row][col] !== pattern[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            for (let j = 0; j < patternLen; j++) {
                const pos = i + j;
                const row = Math.floor(pos / n);
                const col = pos % n;
                horizontalCells.add(row * n + col);
            }
        }
    }
    
    // Find vertical substrings
    for (let j = 0; j < n * m - patternLen + 1; j++) {
        let match = true;
        for (let k = 0; k < patternLen; k++) {
            const pos = j + k;
            const col = Math.floor(pos / m);
            const row = pos % m;
            if (grid[row][col] !== pattern[k]) {
                match = false;
                break;
            }
        }
        if (match) {
            for (let k = 0; k < patternLen; k++) {
                const pos = j + k;
                const col = Math.floor(pos / m);
                const row = pos % m;
                verticalCells.add(row * n + col);
            }
        }
    }
    
    // Count intersection
    let count = 0;
    for (const cell of horizontalCells) {
        if (verticalCells.has(cell)) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-