Command Palette

Search for a command to run...

Hectal
Problem 19.3 · TrieHard

Word Search II

PatternTrie (Prefix Tree)BacktrackingMatrix Traversal

What it teaches: Search many words at once by walking a trie alongside a grid DFS.

Practise it on judges as “Word Search II”.

The problem

Given a grid of letters and a list of words, return every word that can be formed by a path of horizontally or vertically adjacent cells, using each cell at most once per word. Any order.

Example 1

Input: 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]

Constraints

  • 1 ≤ rows, cols ≤ 12
  • 1 ≤ words ≤ 3 × 10⁴

Pattern clues in the wording

  • → Many words, one grid
  • → Paths of adjacent cells

These clues point to Trie (Prefix Tree): Store words character by character in a tree so every prefix is a path you can walk in O(length).

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
["eat","oath"]
2
board = [["a","b"],["c","d"]]
words = ["abcb"]
[]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Trie-guided backtracking · O(cells × 4 × 3^(L−1)) worst case, much less with pruning
1

Trie-guided backtracking

Time O(cells × 4 × 3^(L−1)) worst case, much less with pruning Space O(total characters)

Build a trie storing each word at its end node. From every cell, DFS: follow the child for the cell's letter, record and clear a word if one ends here, mark the cell used, recurse in four directions, then restore it.

Approach 1
import java.util.*;

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        String word;
    }

    public List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node n = root;
            for (char c : w.toCharArray()) {
                if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();
                n = n.next[c - 'a'];
            }
            n.word = w;
        }
        List<String> out = new ArrayList<>();
        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[0].length; c++) dfs(board, r, c, root, out);
        return out;
    }

    private void dfs(char[][] b, int r, int c, Node parent, List<String> out) {
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return;
        char ch = b[r][c];
        if (ch == '#') return;
        Node n = parent.next[ch - 'a'];
        if (n == null) return;                       // no word continues this way: prune
        if (n.word != null) { out.add(n.word); n.word = null; }
        b[r][c] = '#';
        dfs(b, r + 1, c, n, out);
        dfs(b, r - 1, c, n, out);
        dfs(b, r, c + 1, n, out);
        dfs(b, r, c - 1, n, out);
        b[r][c] = ch;
    }
}

Verdict: The standard solution.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Duplicate words in the list
  • A word that is a prefix of another (oath and oat)

Mistakes people make

  • Stopping the DFS after finding a word (a longer word may continue).
  • Reporting the same word twice.

Interview

Follow-up questions

What further pruning helps on large inputs?