FastPrepCount Straight-Line Word Occurrences in a Grid

Count Straight-Line Word Occurrences in a Grid

Visa logoVisa● MediumFULLTIMEOA
Learn

Problem statement

Given a square grid of characters and a nonempty word, count every straight-line occurrence of the word.

An occurrence may run horizontally, vertically, or diagonally in either direction, for a total of eight directions. Matches may overlap, and characters are compared exactly, including case.

Opposite directions are counted separately. Therefore, every palindromic occurrence is counted twice. For a one-character palindrome, count each matching cell twice.

Function

countGridWordOccurrences(grid: String[], word: String) → int

Examples

Example 1

grid = ["ctt","cat","cct"]word = "cat"return = 4

The word appears once across the middle row, once vertically, and twice diagonally, for 4 occurrences.

Example 2

grid = ["ABA","BAB","ABA"]word = "ABA"return = 8

Two rows and two columns spell the palindrome. Each of those four geometric lines is counted in both directions, for 8 occurrences.

Example 3

grid = ["A0","aA"]word = "A"return = 4

Two cells contain uppercase A; each one-character palindromic occurrence counts twice.

Constraints

  • 3 <= grid.length <= 200
  • Every row has exactly grid.length characters.
  • 1 <= word.length <= grid.length
  • The grid and word contain uppercase or lowercase English letters or decimal digits.
  • The answer fits in a 32-bit signed integer.

More Visa problems

See Visa hiring insights
public int countGridWordOccurrences(String[] grid, String word) {
    // Write your solution here.
}
grid["ctt","cat","cct"]
word"cat"
expected4
Checking account…