Backtracking · Grid DFS

Medium · O(m · n · 3^L) time · O(L) space

Problem

You are given an m × n grid of letters board and a string word. Return true if the word can be spelled by walking through the grid. Each step moves to a neighbouring cell: up, down, left or right, never diagonally. A cell can be used at most once in a single spelling.
Example 1 Input: board = [["A","C","B"], ["D","B","C"]], word = "CBCA" Output: true (C at row 1 col 2, B above it, C to its left, then A) Example 2 Input: the same board, word = "CBCC" Output: false (there are only two C cells, and each may be used once)
Constraints 1 ≤ m, n ≤ 6 1 ≤ word.length ≤ 15 board and word contain letters only

Brute force

You have a grid of letters, like a word-search puzzle, and a word. Can you spell the word by walking through the grid? You start on any cell, and each step goes to a neighbour: up, down, left or right, never diagonally. You may not use the same cell twice in one spelling.

  1. The letters of the word must be matched in order, one cell per letter.
  2. Each next cell must be a neighbour of the one before.
  3. The path may start anywhere.
  4. No cell may appear twice in the same path. (A cell may appear in different paths.)

At every cell we ask one question: does this cell hold the letter I need next? If not, this path is dead right here. If yes, the rest of the word must be found from one of its neighbours. So it is a search where the word length limits the depth, and each step has at most four directions.

The straightforward version gives every step its own copy of the cells used so far, so one path can never affect another.

The problem with it

It is correct. The problem is the copying: every step builds a new set of up to L cells (L is the length of the word), which adds extra work to every one of the many steps. It does not need to be this expensive. Because each path carries its own record, going back to the previous cell needs no clean-up, and that is the reason it works. Can one shared record do the same job?

How to think your way to the optimal solution

Keep one record for the whole search, written straight onto the board. When we step onto a cell, we mark it (we overwrite its letter with "#"), so no other step on this path can use it. When we leave the cell, we undo the mark: we put the letter back, so other paths can use that cell again.

This "mark, explore, undo" pattern is called backtracking. The undo line is the important one. The mark must be true only for the cells on the path we are currently exploring.

The search stops as soon as the whole word is matched, and it gives up on a path the moment one letter is wrong. That is what keeps it fast: most paths die within a step or two.

The optimal solution

  1. Try every cell as the start, and ask dfs(r, c, 0): can the word be spelled starting here?
  2. In dfs(r, c, k): k equals the word length⟶every letter matched: return True
  3. the cell is off the board, or its letter is not word[k]⟶return False
  4. Mark the cell with "#". Try the four neighbours with k + 1.
  5. Put the letter back (undo), and return whether any neighbour succeeded.

By hand, on the board [["A","C","B"],["D","B","C"]] with the word "CBCA":

  1. The first cell holding C is (0,1). Mark it. For B we try its neighbours. Down is (1,1), which is B. Mark it, and look for C: its right neighbour (1,2) is C. Mark it, and look for A: its neighbours are a B and the marked cell, so no A. This path is dead.
  2. Undo (1,2), then undo (1,1). Back at (0,1), the next neighbour with a B is (0,2). Its neighbour (1,2) is C, but then there is no A next to it. Dead again. Undo everything. Start (0,1) fails.
  3. The next cell holding C is (1,2). Mark it. Up is (0,2), a B. Mark it. Its left neighbour (0,1) is a C. Mark it. Its left neighbour (0,0) is an A. All four letters matched, so return true.

Press Play to watch the marks and the undo. In the second example, the word needs three C's but the board has only two, so every path ends in false.

Complexity analysis

O(m × n × 3L)
Time. Here's why: there are m × n starting cells. From a start, the first step has up to 4 choices, but every later step has at most 3, because one neighbour is the cell we just came from and is marked. The path is at most L letters long, so there are at most about 3L paths from each start. In practice most paths die early, so it is much faster.
O(L)
Space. The only memory that grows is the chain of nested calls, which is at most as deep as the word is long. The marks live on the board itself.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"Now I give you a whole list of words. Which of them can you find?"

What they are checkingWhether you can see that searching the board once per word repeats work, and know the structure that fixes it. This is the well-known "Word Search II".

A strong answerI would put all the words into a trie, a tree where each path from the top spells the start of some words. Then I run one search over the board, and I walk the trie at the same time. If the letters I have so far are not the start of any word, I stop that path at once. Words that share a start are searched together. When I find a word I can remove it from the trie, so I never report it twice, and so the trie keeps shrinking.

"What goes wrong if you forget the undo line?"

What they are checkingWhether you really understand what the mark means. This is the line a careful interviewer will ask about.

A strong answerThe marks would pile up. After one dead-end path, all its cells would stay as "#", and no later path could use them. So a word that needs one of those cells would be missed, and the function would return false when the answer is true. The mark has to mean "on the path I am on right now", and the undo is what keeps it true.

"Can you reject some inputs without searching at all, or search faster?"

What they are checkingWhether you think about cheap checks before an expensive search.

A strong answerYes. Before searching, I can count the letters on the board. If the word needs more of some letter than the board has, the answer is false right away. A second idea is to start from the end of the word if its first letter is more common on the board than its last, since fewer starting cells means fewer searches. Both are my own reasoning about cutting work. They do not change the worst case, but they often skip the search entirely.

Spot this pattern