String · 24 of 43

Search a Word in a 2D Grid of characters

Find every box in a letter grid where a word starts, reading in a straight line in any of the eight directions, like a word search puzzle.

MediumGrid direction scan

Simple way: time O(R * C * 8 * L)
room O(1)
Clever way: time O(R * C + L)
room O(R + C + L)

The problem, simply

You get a grid of letters with R rows and C columns, and a word of length L. The word may be written in the grid in a straight line in any of eight directions: left, right, up, down, and the four diagonals. It never bends.

Give back every box where the word starts, in reading order (top row first, left to right). If the word starts in the same box in two directions, list that box once.

This is the classic "find the string in a grid" problem. A different problem lets the word bend like a snake, and that one needs backtracking. Here the word is always straight.

A story to remember it

Picture it

grid

Find abe. It starts at three boxes: going down right from (0,0), going down left from (0,2), and going right from (1,0).

answer
path

Examples

Three starts, three directions

In: grid = [abab, abeb, ebeb], word = 'abe'
Out: [[0,0], [0,2], [1,0]]

Down right from (0,0), down left from (0,2), and right from (1,0). The answer is listed in reading order.

Only one way

In: grid = [abc, drf, ghi], word = 'abc'
Out: [[0,0]]

abc is in the top row going right. No other line spells it.

Read backwards

In: grid = [cat, xxx, xxx], word = 'tac'
Out: [[0,2]]

tac starts at the t in the corner and reads to the left. Going left counts as a direction.

Not there

In: grid = [ab, cd], word = 'abcd'
Out: []

The word is longer than any line in a 2 by 2 grid, so it cannot fit. Return an empty list.

Way 1: the simple way

Do what the kid with the finger does.

Visit every box in reading order.
If the box does not hold the first letter, skip it.
Otherwise try the eight directions. For one direction, step letter by letter. Stop if you leave the grid or a letter is wrong.
If all L letters match, add the box to the answer and stop trying more directions for it.

The finger tries every spoke from every a

01 / 10

grid

arraystarts found

Box (0,0) holds a, the first letter. Try the eight directions. The four that go up or left leave the grid at once.

looking now
answer
rejected
path
just added
ignored

java

class Solution {
    // the eight spokes: up-left, up, up-right, left, right, down-left, down, down-right
    int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
    int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

    public List<int[]> searchWord(char[][] grid, String word) {
        List<int[]> out = new ArrayList<>();
        int R = grid.length, C = grid[0].length;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (grid[r][c] != word.charAt(0)) continue;    // wrong first letter
                for (int d = 0; d < 8; d++) {
                    if (fits(grid, word, r, c, d)) {
                        out.add(new int[]{r, c});
                        break;                                 // list each box once
                    }
                }
            }
        }
        return out;
    }

    private boolean fits(char[][] grid, String word, int r, int c, int d) {
        for (int k = 0; k < word.length(); k++) {
            if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return false;
            if (grid[r][c] != word.charAt(k)) return false;   // wrong letter: stop
            r += dr[d];
            c += dc[d];
        }
        return true;
    }
}

How long it takes: every box, times eight directions, times up to L letters, O(R * C * 8 * L). Extra room: a few counters, O(1) besides the answer. This is the answer most interviewers expect.

Way 2: the clever way

Way 1 can read the same box many times. Think of a grid full of a and a word like aaaab: almost every spoke reads four letters before it fails.

The champion reads each straight line once.

Cut the grid into lines: every row, every column, every down right diagonal and every down left diagonal. Each box sits on exactly four lines.
Read each line from one end to the other and look for the word. Reading a line backwards is the same as looking for the word spelled backwards, so search for both word and its reverse.
Use a smart matcher, KMP. It keeps a cheat sheet, the fallback table, that says how much of the word still counts after a wrong letter. Because of it, the reading finger on the line never steps back.
When the forward word matches at line position p, the start box is box p of the line. When the reversed word matches at p, the real word starts at the far end, box p + L - 1.

Read each straight line once

01 / 08

grid

arrayline: row 0

arrayword

Row 0 is one straight line: abab. The line finger i starts at its first box, and the word finger j at the first letter of abe.

seen
done
answer
rejected
path
just added

java

class Solution {
    public List<int[]> searchWord(char[][] grid, String word) {
        int R = grid.length, C = grid[0].length, L = word.length();
        String back = new StringBuilder(word).reverse().toString();
        int[] fwdTable = fallback(word), backTable = fallback(back);
        boolean[][] start = new boolean[R][C];
        int[][] steps = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};  // right, down, down-right, down-left

        for (int[] d : steps) {
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    int pr = r - d[0], pc = c - d[1];
                    if (pr >= 0 && pr < R && pc >= 0 && pc < C) continue; // not the first box of a line
                    List<int[]> cells = new ArrayList<>();
                    StringBuilder line = new StringBuilder();
                    for (int x = r, y = c; x >= 0 && x < R && y >= 0 && y < C; x += d[0], y += d[1]) {
                        cells.add(new int[]{x, y});
                        line.append(grid[x][y]);
                    }
                    for (int p : findAll(line, word, fwdTable)) {
                        int[] cell = cells.get(p);                // word starts here
                        start[cell[0]][cell[1]] = true;
                    }
                    for (int p : findAll(line, back, backTable)) {
                        int[] cell = cells.get(p + L - 1);        // read backwards: starts at the far end
                        start[cell[0]][cell[1]] = true;
                    }
                }
            }
        }
        List<int[]> out = new ArrayList<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                if (start[r][c]) out.add(new int[]{r, c});
        return out;
    }

    // the cheat sheet: for each prefix, the longest part that is also a suffix
    private int[] fallback(String w) {
        int[] t = new int[w.length()];
        for (int i = 1, len = 0; i < w.length(); ) {
            if (w.charAt(i) == w.charAt(len)) t[i++] = ++len;
            else if (len > 0) len = t[len - 1];
            else t[i++] = 0;
        }
        return t;
    }

    // KMP: every place where w starts in text; the text finger never moves back
    private List<Integer> findAll(CharSequence text, String w, int[] t) {
        List<Integer> hits = new ArrayList<>();
        for (int i = 0, j = 0; i < text.length(); ) {
            if (text.charAt(i) == w.charAt(j)) {
                i++;
                j++;
                if (j == w.length()) {
                    hits.add(i - j);
                    j = t[j - 1];
                }
            } else if (j > 0) {
                j = t[j - 1];
            } else {
                i++;
            }
        }
        return hits;
    }
}

How long it takes: there are four kinds of lines, each box sits on one line of each kind, and KMP reads a line in time proportional to its length. Building the two cheat sheets costs O(L). In total O(R * C + L), no matter how long the word is. Extra room: one line at a time and the cheat sheets, O(R + C + L), plus the answer marks.

Watch out for

Listing a box twice. A palindrome like aba can match left and right from the same box. Stop after the first direction that works, or mark starts in a boolean grid.
Walking off the grid. Check the row and column before reading the box, not after.
Forgetting the backwards word in Way 2. Four line kinds only cover four directions. The reversed word covers the other four.
For a backwards match, the start is the last box of the match in line order, not the first.
A word of one letter. Every box with that letter is a start, and both ways handle it.

What interviewers ask next

The snake version, where the word can turn at every letter. Use depth first search with backtracking: mark a box as used, try four neighbors, then unmark it.
Many words at once (LeetCode 212). Put all words in a trie and run one backtracking search that follows trie branches, so shared prefixes are read once.
Count matches instead of listing starts. Same loops, but count every direction that fits instead of stopping at the first.
Why does Way 2 not depend on the word length? KMP never moves the line finger backwards, so each box is read a fixed number of times per line.

Remember this

Grown-up words: the spokes are the eight direction vectors, the straight lines are rows, columns and diagonals, the cheat sheet is the KMP failure function (also called the LPS array), and the smart matcher is the Knuth Morris Pratt string search.