All Words on the Board

HardBacktracking

Problem

A letter board is given as board, an array of equal-length strings. A word can be traced by starting on any cell and moving up, down, left or right, using each cell at most once per word.

Given a list of distinct words, return every word from the list that can be traced on the board, in any order.

Example 1

Input:
board = ["OATH", "ETAE", "IHKR", "IFLV"], words = ["OATH", "PEA", "EAT", "RAIN"]
Output:
["OATH", "EAT"]

"PEA" needs a P, which the board lacks; "RAIN" has no traceable path.

Example 2

Input:
board = ["AB", "CD"], words = ["ABCB"]
Output:
[]

Constraints

  • 1 ≤ rows, cols ≤ 12
  • 1 ≤ words.length ≤ 3 · 10^4
  • 1 ≤ words[i].length ≤ 10
  • Uppercase English letters only; words are distinct.

Hint

Show the first hint

Running the single-word search once per word repeats the same grid walks thousands of times. What do the words share?

Walkthrough

How to approach it

01Clarify before coding

  • Can a word be reported twice? No, each found word once.
  • Can one word reuse a cell? No, but different words may use the same cells.
  • How many words? Up to 30,000, so per-word searching is too slow.

02Brute force

For each word, run the single-word grid search from every cell.

Cost: O(W · R · C · 3^L): for 30,000 words on a 12 × 12 board this repeats nearly identical DFS walks billions of times.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.