Word in Grid - All Occurrences

Problem Overview

The word must appear in a straight line across 8 directions.

Intuition

The word must appear in a straight line across 8 directions. Every grid cell can start a search, but only when it matches the first letter. From there, march with fixed row and column deltas until the word ends or a mismatch hits.

Algorithm

1Define 8 direction offset pairs.
2Scan every cell (i, j). Skip unless mat[i][j] equals word[0].
3For each direction, walk k steps comparing mat to word[k].
4On full match, append [i, j] and stop other directions for that cell.
5Return all starting coordinates found.

Example Walkthrough

Input: grid with row abc, word = "abc"

1. Cell (0,0) is a, matching the first letter.
2. Direction right reads a, then b, then c.
3. Add [0,0] once even if other dirs were possible.

Output: [[0,0]]

Common Pitfalls

• Lines are straight; zig-zag paths are not allowed.
• List each starting coordinate once even if several directions work.
• Check bounds on every step, not only the first cell.
• Prune with the first character before trying all eight directions.

Word in Grid - All Occurrences.java

Java

// Approach: From each cell matching word[0], try all 8 straight directions with
// offset arrays. Walk while characters match. Record the start once per cell.
// Complexity: O(m * n * L) time and O(1) extra space, L = word length.
import java.util.*;

class Solution {

    private static final int[] DR = {-1, -1, -1, 0, 0, 1, 1, 1};
    private static final int[] DC = {-1, 0, 1, -1, 1, -1, 0, 1};

    private boolean matches(char[][] mat, String word, int r, int c, int dr, int dc) {
        int n = mat.length;
        int m = mat[0].length;

        for (int k = 0; k < word.length(); k++) {
            if (r < 0 || r >= n || c < 0 || c >= m || mat[r][c] != word.charAt(k)) {
                return false;
            }
            r += dr;
            c += dc;
        }
        return true;
    }

    public ArrayList<ArrayList<Integer>> searchWord(char[][] mat, String word) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (word.isEmpty()) {
            return result;
        }

        int n = mat.length;
        int m = mat[0].length;
        char first = word.charAt(0);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] != first) {
                    continue;
                }
                for (int d = 0; d < 8; d++) {
                    if (matches(mat, word, i, j, DR[d], DC[d])) {
                        result.add(new ArrayList<>(Arrays.asList(i, j)));
                        break;
                    }
                }
            }
        }
        return result;
    }
}

Was this solution helpful?