Word Search II

hardTrie & Strings418 stepsJava · Python · C++

Find every dictionary word on the grid. Put all words in a trie and DFS from every cell, walking the trie alongside the grid. A path that leaves the trie is abandoned immediately, so all words are searched at once.

▶ Watch the animated trace

Traced input: board = [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]], words = [oath, pea, eat, rain] → ["oath", "eat"]. Original problem: neetcode.io/problems/search-for-word-ii

Complexity

BestO(m·n)

AverageO(m·n·4^L)

WorstO(m·n·4^L)

SpaceO(total chars)

The trie prunes most paths early.

Key idea

Searching each word separately repeats work; the trie shares prefixes.
Store the full word at its end node to collect it directly.
Clear the stored word once found so it's not reported twice.
Mark cells with '#' during the DFS and restore them after.

Common mistakes

Running Word Search I for every word times out.
Reporting duplicates when a word can be found along two paths.

Solution

Java

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

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

void dfs(char[][] b, int r, int c, Node node, List<String> res) {
    if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] == '#') return;
    Node next = node.next[b[r][c] - 'a'];
    if (next == null) return;
    if (next.word != null) {
        res.add(next.word);
        next.word = null;
    }
    char ch = b[r][c];
    b[r][c] = '#';
    dfs(b, r + 1, c, next, res);
    dfs(b, r - 1, c, next, res);
    dfs(b, r, c + 1, next, res);
    dfs(b, r, c - 1, next, res);
    b[r][c] = ch;
}

Python

class Node:
    def __init__(self):
        self.next = {}
        self.word = None


def findWords(board: List[List[str]], words: List[str]) -> List[str]:
    root = Node()
    for w in words:
        cur = root
        for c in w:
            cur = cur.next.setdefault(c, Node())
        cur.word = w
    res = []
    m, n = len(board), len(board[0])

    def dfs(r: int, c: int, node: Node) -> None:
        if r < 0 or c < 0 or r >= m or c >= n or board[r][c] == '#': return
        nxt = node.next.get(board[r][c])
        if nxt is None: return
        if nxt.word is not None:
            res.append(nxt.word)
            nxt.word = None
        ch = board[r][c]
        board[r][c] = '#'
        dfs(r + 1, c, nxt)
        dfs(r - 1, c, nxt)
        dfs(r, c + 1, nxt)
        dfs(r, c - 1, nxt)
        board[r][c] = ch

    for r in range(m):
        for c in range(n):
            dfs(r, c, root)
    return res

C++

struct Node {
    Node* next[26] = {};
    string word;
};

void dfs(vector<vector<char>>& b, int r, int c, Node* node, vector<string>& res) {
    if (r < 0 || c < 0 || r >= (int)b.size() || c >= (int)b[0].size() || b[r][c] == '#') return;
    Node* next = node->next[b[r][c] - 'a'];
    if (!next) return;
    if (!next->word.empty()) {
        res.push_back(next->word);
        next->word.clear();
    }
    char ch = b[r][c];
    b[r][c] = '#';
    dfs(b, r + 1, c, next, res);
    dfs(b, r - 1, c, next, res);
    dfs(b, r, c + 1, next, res);
    dfs(b, r, c - 1, next, res);
    b[r][c] = ch;
}

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    Node* root = new Node();
    for (auto& w : words) {
        Node* cur = root;
        for (char c : w) {
            if (!cur->next[c - 'a']) cur->next[c - 'a'] = new Node();
            cur = cur->next[c - 'a'];
        }
        cur->word = w;
    }
    vector<string> res;
    for (int r = 0; r < (int)board.size(); r++)
        for (int c = 0; c < (int)board[0].size(); c++)
            dfs(board, r, c, root, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No words found 'b' can't be reused.	`board = [[a,b],[c,d]], words = [abcb]`	`[]`
Same word twice in the list Reported once.	`board = [[a]], words = [a, a]`	`["a"]`