Word Search II

NeetCode: Word Search II · LeetCode: 212. Word Search II · Difficulty: Hard

Given a grid of letters and a list of words, return all words that can be formed by walking through adjacent cells (up, down, left, right), using each cell at most once per word.

Example

Text

board = [["o","a","a","n"],
         ["e","t","a","e"],
         ["i","h","k","r"],
         ["i","f","l","v"]]
words = ["oath", "pea", "eat", "rain"]
Output: ["eat", "oath"]

Brute force: search the board once per word

For each word, try every starting cell and run a depth-first search that follows the word's letters, marking cells visited on the current path.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    private boolean exists(char[][] board, int r, int c, String word, int idx) {
        if (board[r][c] != word.charAt(idx)) {
            return false;
        }
        if (idx == word.length() - 1) {
            return true;
        }
        char saved = board[r][c];
        board[r][c] = '#';
        boolean found = false;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nc >= 0 && nr < board.length && nc < board[0].length
                    && exists(board, nr, nc, word, idx + 1)) {
                found = true;
                break;
            }
        }
        board[r][c] = saved;
        return found;
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            boolean hit = false;
            for (int r = 0; r < board.length && !hit; r++) {
                for (int c = 0; c < board[0].length && !hit; c++) {
                    hit = exists(board, r, c, word, 0);
                }
            }
            if (hit) {
                result.add(word);
            }
        }
        Collections.sort(result);
        return result;
    }
}

public class Main {
    static char[][] grid(String... rows) {
        char[][] g = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            g[i] = rows[i].toCharArray();
        }
        return g;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        char[][] board = grid("oaan", "etae", "ihkr", "iflv");
        System.out.println(s.findWords(board, new String[]{"oath", "pea", "eat", "rain"}));
    }
}

Output

[eat, oath]

Time: O(W · m · n · 4^L)-ish: every word repeats the full grid search. Space: O(L) recursion. The board is edited in place during the search and restored on the way back, so the same char[][] serves every word.

Optimal: one DFS guided by a trie of all words

Put all words in a trie, then walk the grid once. From each cell, follow the trie edge for the cell's letter and stop at once if no word continues with that letter. Words with a common prefix share work, and dead paths are cut early. When a trie node completes a word, record it and set word to null so it is reported only once. A node is a HashMap of children plus a word field that is null until a word ends at that node. Nodes are linked by object references, so no wrapper type is needed.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    String word; // null until a word ends at this node
}

class Solution {
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> found) {
        char ch = board[r][c];
        TrieNode next = node.children.get(ch);
        if (next == null) {
            return; // '#' (visited) never matches, and neither does a dead end
        }
        if (next.word != null) {
            found.add(next.word);
            next.word = null; // report each word once
        }
        board[r][c] = '#'; // mark visited
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nc >= 0 && nr < board.length && nc < board[0].length) {
                dfs(board, nr, nc, next, found);
            }
        }
        board[r][c] = ch; // undo
    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                node = node.children.computeIfAbsent(ch, k -> new TrieNode());
            }
            node.word = word;
        }
        List<String> found = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root, found);
            }
        }
        Collections.sort(found);
        return found;
    }
}

public class Main {
    static char[][] grid(String... rows) {
        char[][] g = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            g[i] = rows[i].toCharArray();
        }
        return g;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        char[][] board = grid("oaan", "etae", "ihkr", "iflv");
        System.out.println(s.findWords(board, new String[]{"oath", "pea", "eat", "rain"}));
        System.out.println(s.findWords(grid("ab"), new String[]{"ab", "ba", "abc"}));
    }
}

Output

[eat, oath]
[ab, ba]

Time: O(m · n · 4^L) at worst, where L is the longest word, but usually far less because of pruning. Space: O(total letters in words) for the trie.

Optional optimization: remove a trie node once it has no children left, so finished branches are never walked again.

How to explain it in an interview

Say first: "For each word run Word Search I from every cell: O(W · m · n · 4^L), repeating the grid search per word."
Key insight: Search for all words at once. A trie lets one DFS follow the board and the shared word prefixes together, and abandon a path the moment no word starts with it.
Code it in steps: (1) a small TrieNode class with children and word; (2) insert every word; (3) dfs(r, c, node): look up the cell's letter among node.children, return if get gives null; (4) if next.word is not null, add it to the results and set it to null; (5) mark the cell #, recurse into 4 neighbours, restore the cell.
Complexity to state: O(m · n · 4^L) worst case, usually far less; trie space is the total number of letters.
Likely follow-ups / pitfalls: "Duplicates in the output?" set the word to null after reporting it, so it is reported once. "Still slow on big inputs?" Prune exhausted trie nodes. Forgetting to restore the cell is the classic bug.