Search a word in a 2D grid of characters

Medium

Problem

Given a grid of characters and a word, find every cell from which the word can be read in a straight line in any of the 8 directions (horizontal, vertical or diagonal) without changing direction.

Example 1

Input:  grid = ["GEEKSFORGEEKS", "GEEKSQUIZGEEK", "IDEQAPRACTICE"], word = "GEEKS"
Output: [(0,0), (0,8), (1,0)]

Also asked as: Search a Word in a 2D Grid of characters · Count of number of given string in 2D character array

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. DFS from every cell in 8 directions

Time O(R·C·8·L)Space O(1)

From each cell that matches word[0], walk in a fixed direction matching subsequent characters.

function findWord(grid, word) {
const R = grid.length, C = grid[0].length;
const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
const hits = [];
const ok = (r, c, dr, dc) => {
for (let k = 0; k < word.length; k++) {
const nr = r + dr * k, nc = c + dc * k;
if (nr < 0 || nc < 0 || nr >= R || nc >= C || grid[nr][nc] !== word[k]) return false;
}
return true;
};
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
if (grid[r][c] === word[0])
for (const [dr, dc] of dirs)
if (ok(r, c, dr, dc)) hits.push([r, c, dr, dc]);
return hits;
}