Word Search II

The problem

You are given a grid of letters board with m rows and n columns, and a list of different words. Return every word from the list that can be spelled on the board.

A word is spelled by a path of cells. Each next cell must touch the previous one on a side: up, down, left or right, not diagonally. One path may not use the same cell twice. The answer can be in any order.

Example 1

Input: board = [["c","a","t"], ["o","r","e"]], words = ["cat", "core", "toe"]

Output: ["cat", "core"]

“cat” runs along the top row. “core” goes down from c, then right through r and e. “toe” fails: no “o” touches the t.

	0	1	2
0	c	a	t
1	o	r	e

Example 2

Input: board = [["a","b"], ["c","d"]], words = ["abd", "acb"]

Output: ["abd"]

a, b, d is a path. In “acb”, the c and the b only touch diagonally.

Example 3

Input: board = [["x"]], words = ["x", "xx"]

Output: ["x"]

“xx” would need the single cell twice.

Constraints

• 1 ≤ m, n ≤ 12
• 1 ≤ words.length ≤ 30,000 (call this W)
• 1 ≤ words[i].length ≤ 10 (call the longest L)
• Only lowercase letters. All words are different.

Clarifying questions

Do diagonal cells count as touching?

No. Only up, down, left and right.

Can a path reuse a cell?

Not within one word. Different words may use the same cells.

Can a word be found twice?

It may be spelled in two places, but it must appear in the answer only once.

Does the order of the answer matter?

No. Any order is fine.

Why does the number of words matter?

There can be 30,000 of them. Searching the board once per word is what makes the simple way too slow.

Spot the pattern

Spelling one word on a grid is backtracking: step to a neighbor, go on, and undo the step when the path fails. With many words, most of them share starts, like “cat” and “core”. A trie of all words lets one search serve them all, and it tells at each step whether any word still starts this way.

Solutions

Brute forceO(W × m × n × 3ᴸ)TrieO(m × n × 3ᴸ)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(W × m × n × 3ᴸ)

The idea

Solve the one-word problem, Word Search, once for every word. For a word, try every cell as the start. From a cell that holds the right letter, mark it as used, try the four neighbors for the next letter, and unmark it when done. If some start spells the whole word, add it to the answer.

It is correct, but the work is repeated. Every word searches the whole board again from zero, even when many words share the same first letters.

Walkthrough

	0	1	2
0	c	a	t
1	o	r	e

found

empty

1. for word in words:
2. if any(exists(row, column, word, 0) for every cell): found.append(word)
3. def exists(row, column, word, position):
4. if position == len(word): return True
5. if outside or board[row][column] != word[position]: return False
6. board[row][column] = "#"
7. found_rest = any(exists(next_row, next_column, word, position + 1) for the 4 neighbors)
8. board[row][column] = word[position]
9. return found_rest

The brute force handles one word at a time. For each word, it tries to spell it starting from every cell, moving up, down, left or right.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private char[][] board;

    // Brute force: run a separate grid search for every word, from every
    // cell. W words, m * n starts each, and up to 4 * 3^(L-1) steps per start.
    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        List<String> found = new ArrayList<>();
        for (String word : words) {
            search:
            for (int row = 0; row < board.length; row++)
                for (int column = 0; column < board[0].length; column++)
                    if (exists(row, column, word, 0)) {
                        found.add(word);
                        break search;
                    }
        }
        return found;
    }

    private boolean exists(int row, int column, String word, int position) {
        if (position == word.length()) return true;
        if (row < 0 || row >= board.length || column < 0 || column >= board[0].length
            || board[row][column] != word.charAt(position)) return false;
        // Block this cell so the same path cannot use it twice.
        board[row][column] = '#';
        boolean foundRest = exists(row + 1, column, word, position + 1)
            || exists(row - 1, column, word, position + 1)
            || exists(row, column + 1, word, position + 1)
            || exists(row, column - 1, word, position + 1);
        // Undo, so the next search sees the board as it was.
        board[row][column] = word.charAt(position);
        return foundRest;
    }
}

Big O

Time O(W × m × n × 3ᴸ)Space O(L)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion, so we count the calls of exists. Each call checks one cell against one letter and starts up to 4 more calls. That is a fixed job, so each call counts as 1 step.

   1. for word in words:
   2. if any(exists(row, column, word, 0) for every cell): found.append(word)
   3. def exists(row, column, word, position):
   4. if position == len(word): return True
   5. if outside or board[row][column] != word[position]: return False
   6. board[row][column] = "#"
   7. found_rest = any(exists(next_row, next_column, word, position + 1) for the 4 neighbors)
   8. board[row][column] = word[position]
   9. return found_rest

2. 2 Count the runs on Example 1

   The table counts the calls of exists per word, including the calls that stop at once on a wrong letter or the edge of the board. Each search stops as soon as a start spells the word.

   8 + 9 + 10 = 27 calls.

   word	"cat"	"core"	"toe"
   exists() calls	8	9	10

   total

   8 + 9 + 10 = 27 calls

3. 3 Write the count for any n

   For one start, the first letter can go 4 ways. Every later step can go at most 3 ways, because the cell it came from is blocked. A word of length L makes at most 4 × 3^(L−1) calls from one start. There are m × n starts and W words:

   W × m × n × 4 × 3^(L−1) calls

   Check it with Example 1: the bound for “core” alone is 6 × 4 × 27 = 648. The real search used 9, because wrong letters stop most paths at once. Big O counts the worst case, such as a board full of “a” and words like “aaaaaaaaab”.

4. 4 Keep only the part that grows fastest

   Drop the 4 and the 1 in the power. 4 × 3^(L−1) is the same as (4/3) × 3ᴸ, a constant times 3ᴸ. What is left is W × m × n × 3ᴸ. With W up to 30,000, this is far too slow.

   So the time is O(W × m × n × 3ᴸ).

5. S Space: count the extra memory the same way

   Only one path is open at a time, so the call stack is at most L + 1 deep. The board is marked in place, so no copy is needed. The space is O(L), plus the answer list.

   call stack (L frames)found

Trie O(m × n × 3ᴸ)

The idea

Put all the words in a trie first: a tree where each edge is one letter and a node remembers the word that ends there.

Then search the board once. From every cell, walk the grid and the trie together. Stepping onto a cell means following that letter’s edge in the trie. If the edge does not exist, no word starts with the letters on this path, so stop at once. That check is what makes this fast: a path dies as soon as it spells something that no word begins with.

When the trie node holds a word, add it to the answer and clear it, so it is not added twice. Then keep going, because a longer word may continue from the same path.

Why it never misses the answer: every word is one path in the trie. The search tries every board path that is also a trie path, from every start cell, and it only stops paths that no word could follow.

Walkthrough

	0	1	2
0	c	a	t
1	o	r	e

found

empty

1. root = trie(words)
2. for row, column in every cell:
3. explore(row, column, root)
4. def explore(row, column, node):
5. letter = board[row][column]
6. if letter not in node.children: return
7. node = node.children[letter]
8. if node.word: found.append(node.word); node.word = None
9. board[row][column] = "#"
10. for (next_row, next_column) in the neighbors inside the board:
11. explore(next_row, next_column, node)
12. board[row][column] = letter

Put all words in one trie first. Then search the board once: from every cell, walk the grid and the trie together.

← BackStep →Play1 / 15

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private static class Node {
        Node[] children = new Node[26];
        // The word that ends here, or null.
        String word;
    }

    private char[][] board;
    private final List<String> found = new ArrayList<>();

    // Trie of all words, then one grid search from every cell. The trie says
    // at once when a path can no longer spell any word, so all words share one search.
    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        Node root = new Node();
        for (String word : words) {
            Node node = root;
            for (char letter : word.toCharArray()) {
                if (node.children[letter - 'a'] == null) node.children[letter - 'a'] = new Node();
                node = node.children[letter - 'a'];
            }
            node.word = word;
        }
        for (int row = 0; row < board.length; row++)
            for (int column = 0; column < board[0].length; column++) explore(row, column, root);
        return found;
    }

    private void explore(int row, int column, Node node) {
        char letter = board[row][column];
        // No word continues with this letter, so stop here.
        if (letter == '#' || node.children[letter - 'a'] == null) return;
        node = node.children[letter - 'a'];
        if (node.word != null) {
            found.add(node.word);
            // Remove it, so the same word is not reported twice.
            node.word = null;
        }
        // Block this cell so the same path cannot use it twice.
        board[row][column] = '#';
        if (row + 1 < board.length) explore(row + 1, column, node);
        if (row > 0) explore(row - 1, column, node);
        if (column + 1 < board[0].length) explore(row, column + 1, node);
        if (column > 0) explore(row, column - 1, node);
        board[row][column] = letter;
    }
}

Big O

Time O(m × n × 3ᴸ)Space O(W × L)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are two parts. Building the trie takes one step per letter of each word. The search repeats through recursion: each call of explore checks one cell against one trie edge and starts up to 4 more calls. Each letter and each call counts as 1 step.

   1. root = trie(words)
   2. for row, column in every cell:
   3. explore(row, column, root)
   4. def explore(row, column, node):
   5. letter = board[row][column]
   6. if letter not in node.children: return
   7. node = node.children[letter]
   8. if node.word: found.append(node.word); node.word = None
   9. board[row][column] = "#"
   10. for (next_row, next_column) in the neighbors inside the board:
   11. explore(next_row, next_column, node)
   12. board[row][column] = letter

2. 2 Count the runs on Example 1

   Building the trie walks the letters of “cat”, “core” and “toe”: 3 + 4 + 3 = 10. The search makes 22 calls of explore: 6 start cells, plus every step to a neighbor inside the board. The cells a, o, r and e stop at once, because no word starts with them.

   10 + 22 = 32 steps.

   	trie letters	explore() calls
   steps	10	22

   total

   10 + 22 = 32 steps

3. 3 Write the count for any n

   Building the trie costs at most W × L steps. From each of the m × n cells, one search makes at most 4 × 3^(L−1) calls, for the same reason as before. But now it serves every word at once:

   W × L + m × n × 4 × 3^(L−1) steps

   Check it with Example 1: the bound is 3 × 4 + 6 × 4 × 27 = 660. The real run used 32, because the trie stopped almost every path after one or two letters.

4. 4 Keep only the part that grows fastest

   The factor W is gone from the search: one search now does the work of all W. The trie part, W × L, is there too, but L is at most 10, so it grows only like the input itself. The search term usually dominates, so the time is written O(m × n × 3ᴸ), with the trie build of O(W × L) on top.

   So the time is O(m × n × 3ᴸ).

5. S Space: count the extra memory the same way

   The trie holds at most one node per letter of all words, so W × L nodes. The call stack is at most L + 1 deep. So the space is O(W × L).

   trie (one node per letter)call stack (L frames)found

Common mistake

Stopping when a word is found

Returning right after finding “car” would miss “card” on the same path. Record the word, clear it from the trie, and keep searching from that cell.

Tested at the limits

2,000 random boards of up to 4 x 4 letters from a, b and c, with up to 8 words of 1 to 6 letters. The brute force and the trie found the same set of words every time.

Largest inputs	Result
A 12 x 12 board and 30,000 words (the most allowed), every cell a and every word starting with many a letters. Trie.	1.2 s, and about 6 MB of extra memory. The trie never rules a path out early, so every cell starts a search 10 letters deep.
A 12 x 12 board and 30,000 words of random letters. Trie.	0.08 s, and about 12 MB of extra memory: the trie holds the letters of all the words, which is the O(W × L) space.