Get started

Word Search II — Hard Problem & Solution

board is an m x n grid of lowercase letters given as m strings, and words is a list of distinct lowercase words.

Problem statement

board is an m x n grid of lowercase letters given as m strings, and words is a list of distinct lowercase words.

A word can be formed on the board if its letters can be read along a path of cells where each step moves to a horizontally or vertically adjacent cell, and no cell is used more than once in that word.

Return every word of words that can be formed, sorted in ascending lexicographic order.

Example 1

Input: board = ["code","tarx","kibo"], words = ["cod","dex","bra","kit","tack","oar","box"]
Output: ["box","bra","cod","dex","oar"]
Explanation: `kit` fails because no `t` touches the `i`, and `tack` because no `c` touches the `a`.

Example 2

Input: board = ["ab","cd"], words = ["abdc","abcd","acdb"]
Output: ["abdc","acdb"]
Explanation: `abcd` would need `b` next to `c`, but they touch only diagonally.

Example 3

Input: board = ["a"], words = ["aa"]
Output: []
Explanation: A cell cannot be used twice in one word.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i] consists of lowercase English letters
  • 1 <= words.length <= 3 * 10^4
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters
  • all the strings of words are unique

How to solve Word Search II

Walk the board and a trie of the words in lockstep: the trie tells the DFS which next letters can still lead to a word, so hopeless paths are abandoned immediately.

Approach

  1. Insert every word into a trie; store the word (or its index) at the node where it ends.
  2. From every cell, start a DFS with the trie root. At cell (r, c) move to the child for its letter; if there is none, return.
  3. If that child ends a word, add the word to the answer and clear the marker (so it is not added twice).
  4. Mark the cell as used, recurse into the four neighbours with the child node, then unmark it.
  5. Sort the answer.

Why it works

A word is found exactly when some path of distinct adjacent cells spells it, and the DFS explores every such path whose letters stay inside the trie — any path leaving the trie cannot be a prefix of a word, so pruning it loses nothing. Clearing the end marker reports each word once even if it can be formed in several ways.

Complexity

  • Time — O(m · n · 4 · 3^(L-1)) in the worst case, L = the longest word length
  • Space — O(total length of the words) for the trie

Pitfalls

  • A cell may be reused across different words, but not within one word — unmark it when backtracking.
  • Without clearing the end marker, a word that can be formed along two paths is reported twice.
  • The answer must be sorted; the DFS finds words in board order.

Reference solution

Python

from typing import List

def findWords(board: List[str], words: List[str]) -> List[str]:
    m, n = len(board), len(board[0])
    g = [list(row) for row in board]
    root = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node['$'] = w
    found = []

    def dfs(r, c, parent):
        ch = g[r][c]
        node = parent.get(ch)
        if node is None:
            return
        if '$' in node:
            found.append(node.pop('$'))
        g[r][c] = '#'
        if r > 0:
            dfs(r - 1, c, node)
        if r + 1 < m:
            dfs(r + 1, c, node)
        if c > 0:
            dfs(r, c - 1, node)
        if c + 1 < n:
            dfs(r, c + 1, node)
        g[r][c] = ch

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

JavaScript

var findWords = function(board, words) {
    var m = board.length, n = board[0].length;
    var g = board.map(function(row) { return row.split(''); });
    var next = [new Array(26).fill(0)], end = [-1];
    for (var w = 0; w < words.length; w++) {
        var node = 0;
        for (var i = 0; i < words[w].length; i++) {
            var ch = words[w].charCodeAt(i) - 97;
            if (!next[node][ch]) { next.push(new Array(26).fill(0)); end.push(-1); next[node][ch] = next.length - 1; }
            node = next[node][ch];
        }
        end[node] = w;
    }
    var found = [];
    var dfs = function(r, c, parent) {
        var letter = g[r][c];
        if (letter === '#') return;
        var cur = next[parent][letter.charCodeAt(0) - 97];
        if (!cur) return;
        if (end[cur] >= 0) { found.push(words[end[cur]]); end[cur] = -1; }
        g[r][c] = '#';
        if (r > 0) dfs(r - 1, c, cur);
        if (r + 1 < m) dfs(r + 1, c, cur);
        if (c > 0) dfs(r, c - 1, cur);
        if (c + 1 < n) dfs(r, c + 1, cur);
        g[r][c] = letter;
    };
    for (var r = 0; r < m; r++) for (var c = 0; c < n; c++) dfs(r, c, 0);
    found.sort();
    return found;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 424 strings problems · the whole catalogue

Learn the technique: Strings · Matrix and Grid Traversal