Count cells in overlapping horizontal and vertical substrings

Array String Rolling Hash String Matching Matrix Hash Function

27.0% acceptance

Feb 25, 2026

You are given an m x n matrix grid and a string pattern. Count cells that are part of at least one horizontal substring match AND at least one vertical substring match. Horizontal: left-to-right row by row linearization. Vertical: top-to-bottom column by column linearization.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_cells(grid: Vec<Vec<char>>, pattern: String) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let total = m * n;
    let pat: Vec<u8> = pattern.bytes().collect();
    let p = pat.len();

    let mut h_seq = Vec::with_capacity(total);
    for r in 0..m {
      for c in 0..n {
        h_seq.push(grid[r][c] as u8);
      }
    }
    let mut v_seq = Vec::with_capacity(total);
    for c in 0..n {
      for r in 0..m {
        v_seq.push(grid[r][c] as u8);
      }
    }

    // --- horizontal coverage via difference array (O(total) instead of O(total*p)) ---
    let mut h_diff = vec![0i32; total + 1];
    kmp_mark(&h_seq, &pat, |start| {
      h_diff[start] += 1;
      h_diff[start + p] -= 1;
    });
    let mut hm = vec![false; total];
    let mut sum = 0i32;
    for i in 0..total {
      sum += h_diff[i];
      hm[i] = sum > 0;
    }

    // --- vertical coverage via difference array ---
    let mut v_diff = vec![0i32; total + 1];
    kmp_mark(&v_seq, &pat, |start| {
      v_diff[start] += 1;
      v_diff[start + p] -= 1;
    });
    let mut vm = vec![false; total];
    sum = 0;
    for pos in 0..total {
      sum += v_diff[pos];
      if sum > 0 {
        let c = pos / m;
        let r = pos % m;
        vm[r * n + c] = true;
      }
    }

    (0..total).filter(|&i| hm[i] && vm[i]).count() as i32
  }
}

fn kmp_mark(text: &[u8], pat: &[u8], mut f: impl FnMut(usize)) {
  let n = text.len();
  let p = pat.len();
  if p == 0 || p > n { return; }

  let mut fail = vec![0usize; p];
  let mut j = 0usize;
  for i in 1..p {
    while j > 0 && pat[i] != pat[j] { j = fail[j - 1]; }
    if pat[i] == pat[j] { j += 1; }
    fail[i] = j;
  }

  let mut j = 0usize;
  for i in 0..n {
    while j > 0 && text[i] != pat[j] { j = fail[j - 1]; }
    if text[i] == pat[j] { j += 1; }
    if j == p {
      f(i + 1 - p);
      j = fail[j - 1];
    }
  }
}