Search a word in a 2D grid of characters
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.
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;}