Word Search

The problem

You are given a grid of letters board with m rows and n columns, and a word. Return true if the word can be spelled on the board, and false if not.

The letters must come from a path of cells where each next cell touches the previous one on a side: up, down, left or right. Diagonal steps are not allowed, and no cell may be used twice in the same word.

Example 1

Input: board = [["s","e","a"], ["e","o","t"], ["r","d","n"]], word = "sea"

Output: true

The top row spells s, e, a from left to right. The “e” below the “s” is a trap: no “a” touches it.

	0	1	2
0	s	e	a
1	e	o	t
2	r	d	n

Example 2

Input: board = [["a","b"], ["c","d"]], word = "abdc"

Output: true

Go right to b, down to d, then left to c.

Example 3

Input: board = [["a","b"], ["c","d"]], word = "aba"

Output: false

The second “a” would have to be the same cell as the first.

Constraints

• 1 ≤ m, n ≤ 6
• 1 ≤ word.length ≤ 15 (call this L)
• Only upper and lower case English letters.

Clarifying questions

Do diagonal cells count as neighbors?

No. Only the four cells that share a side.

Can a cell be used twice?

No, not in one word. That is why the path must be marked while we search.

Are upper and lower case the same letter?

No. "A" and "a" are different, so compare letters exactly.

Can we change the board?

We may mark it while searching, as long as we put every letter back.

Spot the pattern

From one cell there are up to four ways to go, and from there up to three more, and so on. We need to try these paths one by one and give up on a path as soon as a letter does not match. Choosing a step, going deeper, and undoing the step when it fails is backtracking.

Solutions

BacktrackingO(m × n × 3ᴸ)

Show all

There is only one approach worth showing. Listing every path of the board first would be far bigger, and this search already stops each path at the first wrong letter.

Backtracking O(m × n × 3ᴸ)

The idea

Try every cell as the start. From a start, run a search explore(row, column, position) that asks: can the rest of the word, from letter position on, be spelled starting at this cell?

• If position is past the last letter, the whole word is spelled: return true.
• If the cell is outside the board, already on the path, or holds the wrong letter, return false.
• Otherwise, block the cell by writing # into it, so the rest of the path cannot step on it again. Ask the same question for letter position + 1 at each of the four neighbors. Then write the letter back, whatever the answer was, so other paths can use the cell.

The search stops as soon as one path works.

Why it never misses the answer: if the word is on the board, its path starts at some cell and takes one of the four steps each time. The search tries every start and every step, and only drops a step when it cannot be part of a valid path.

Walkthrough

	0	1	2
0	s	e	a
1	e	o	t
2	r	d	n

matched

-

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

Look for "sea". Try every cell as the start. From a cell, the next letter must be right above, below, left or right of it.

← BackStep →Play1 / 10

Code

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

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private char[][] board;
    private String word;

    // Backtracking: from every cell, try to spell the word step by step,
    // marking the path so no cell is used twice, and unmarking it on the way back.
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        for (int row = 0; row < board.length; row++)
            for (int column = 0; column < board[0].length; column++)
                if (explore(row, column, 0)) return true;
        return false;
    }

    private boolean explore(int row, int column, int position) {
        // Every letter matched.
        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 rest of the path cannot reuse it.
        board[row][column] = '#';
        boolean found = explore(row + 1, column, position + 1)
            || explore(row - 1, column, position + 1)
            || explore(row, column + 1, position + 1)
            || explore(row, column - 1, position + 1);
        // Undo, so other paths can still use this cell.
        board[row][column] = word.charAt(position);
        return found;
    }
}

Big O

Time O(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 explore. Each call checks one cell against one letter and, if it matches, starts four more calls. That is a fixed job, so each call counts as 1 step.

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

2. 2 Count the runs on Example 1

   Example 1 finds the word from the first cell. The start is 1 call. Stepping down to the “e” below it is 1 more, and that “e” makes 4 calls that all fail. Stepping up is outside the board: 1 call. Stepping right reaches the “e” that works: 1 call. It makes 3 calls, and the third one is the “a”. The “a” makes one last call that sees the word is complete.

   1 + 1 + 4 + 1 + 1 + 3 + 1 = 12 calls.

   start	row 0, col 0
   explore() calls	12

3. 3 Write the count for any n

   From one start, the first step can go 4 ways. Every later step can go at most 3 ways, because the cell it came from is blocked. A path is at most L letters long, so one start makes at most about 4 × 3^(L−1) calls. There are m × n starts:

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

   Check it with Example 1: the bound is 9 × 4 × 9 = 324. The real run used 12, because most paths failed on their first wrong letter. The worst case is a board full of “a” and a word like “aaaaab”.

4. 4 Keep only the part that grows fastest

   4 × 3^(L−1) is (4/3) × 3ᴸ, a constant times 3ᴸ. Drop the 4/3. What is left is m × n × 3ᴸ. It is exponential in L, which is fine because L is at most 15 and the board at most 6 × 6.

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

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

   The board is marked in place, so no copy and no set of visited cells is needed. The only memory is the call stack, which holds one call per letter of the current path: at most L + 1. So the space is O(L).

   call stack (L + 1 deep)

Common mistake

Forgetting to unblock the cell

If the code leaves # in a cell after a failed path, later paths cannot use that cell, and real answers get missed. Put the letter back before returning, on success and on failure.

Tested at the limits

2,000 random boards of up to 4 x 4 cells filled with a, A and b, and words of 1 to 7 letters. Paths that would need a cell twice and upper and lower case mismatches come up often. The backtracking gave the same answer every time as a simple check that tries every path of different cells.

Largest inputs	Result
A 6 x 6 board of all A (the most allowed), and a 15-letter word of 14 A then B. The word is not there, so every start tries every path of A before it gives up. Backtracking.	About 2.3 s, and about 0.01 MB of extra memory: only the path of up to 15 calls, because cells are blocked on the board itself.