236. Search a Word in a 2D Grid of Characters

Given an R x C grid of lowercase letters and a word, print 'Yes' if the word can be found by starting at some cell and reading consecutive characters in a straight line in one of the 8 directions (up, down, left, right, and the four diagonals) without going out of bounds, otherwise print 'No'. The first line of input is R and C; the next R lines are the grid's rows; the last line is the word.

Input: The first line contains two integers R and C. Each of the next R lines contains a row of C lowercase letters. The final line contains the word to search for. Output: Print 'Yes' if the word can be found in a straight line in any of the 8 directions, otherwise print 'No'.

1 <= R, C <= 100, 1 <= |word| <= 100

This 8-direction variant is a meaningfully different (and generally harder-feeling) problem than the row/column-only 2D string search - conflating the two is a common mistake, so always re-check exactly which directions a given problem allows.

Check whether a word can be found in a grid of letters by starting somewhere and reading in a straight line, in any of the 8 possible directions. Brute force: This IS essentially the brute-force approach already (try every starting cell and every direction) - there isn't a fundamentally faster general algorithm for a single-word search like this, since in the worst case you must examine most of the grid. Optimised: The main efficiency gain available is stopping EARLY the moment a direction's characters stop matching (rather than continuing to check the rest of that direction pointlessly), and only starting extension attempts from cells that already match the word's first character - both prune away the vast majority of unnecessary checks without changing the fundamental worst-case complexity.

First do a single scan of the grid to collect only the coordinates of cells whose character matches the word's first character - these are the only cells that could possibly start a valid match. Then, only from these candidate cells, try the 8 directions with the same fail-fast character-by-character comparison used above. Combining candidate-filtering with early termination minimizes both the number of starting points considered and the work spent per attempt; the worst case can't beat O(R*C*|word|) since some input could still force checking most of the grid, but average-case work drops substantially compared to blindly trying all R*C cells. Time: O(R * C * 8 * |word|) worst case, much faster in practice Space: O(1)

Keep the same 8-directions-per-cell strategy, but fail fast: check characters one at a time along a direction and stop immediately at the first mismatch instead of assuming you must always compare the full word length; also skip a starting cell immediately if its own character doesn't match the word's first character, without even setting up the 8 direction loops for it. This avoids the large fraction of wasted work brute force spends comparing walks that were doomed from the very first or second character, while remaining correct for every case. Time: O(R * C * 8 * |word|) worst case, faster in practice Space: O(1)

For every cell (i, j) in the grid and each of the 8 possible directions, walk outward from (i, j) comparing each grid character against the corresponding character of the word; if all |word| characters match without going out of bounds, the word is found. This checks literally every starting point and direction combination directly against the definition of the problem, and is simple to get right, but it does a full length-of-word comparison from every cell regardless of how quickly a mismatch could have been detected. Time: O(R * C * 8 * |word|) Space: O(1)

1. For every cell in the grid that matches the word's FIRST character, try extending outward in each of the 8 possible directions (up, down, left, right, and the 4 diagonals). 2. For each direction, check whether the subsequent characters of the word match the grid's characters continuing in that exact direction, stopping the moment there's a mismatch or you go out of bounds. 3. If any starting cell and direction successfully matches the ENTIRE word, answer Yes.

Time: O(R * C * |word|) in the worst case - for each of the R*C cells, up to 8 directions are tried, each checked up to |word| characters deep. Space: O(1) extra space - no additional grid or structure needed beyond the input itself.

A word found only along a diagonal direction; a word longer than max(R, C), which must still be checked rather than ruled out prematurely; R, C up to 100 and word length up to 100 for performance.

Be careful that a long word CAN still be found along a diagonal even if it's longer than both R and C individually - don't prematurely rule out searching based on grid dimensions alone, always check all 8 directions properly from every matching starting cell.