Skip to content
RED SAGSkills
hard60 ptstriebacktrackingmatrix

Find Every Dictionary Word on the Board

A word game shows a letter board as an array of equal-length strings board (one per row). A word is on the board if it can be traced by starting on any cell and stepping up, down, left or right, never reusing a cell within the same word.

Given a list of distinct words, return all of those found on the board, sorted in ascending order. Searching the board once per word is too slow for the big tests; put the words in a trie and walk the board and the trie together.

Example 1

Input: board = ["CATS","ROPE","ENDS"], words = ["CROP","SEPT","OPEN","POND","CAT","DOG","ROPES"]
Output: ["CAT","CROP","POND","ROPES","SEPT"]
Explanation: DOG and OPEN cannot be traced.

Example 2

Input: board = ["AB","CD"], words = ["ABDC","ACDB","ABCD","BA"]
Output: ["ABDC","ACDB","BA"]
Explanation: ABCD would need a diagonal step.

Constraints

  • 1 <= rows, cols <= 12
  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 10
  • Uppercase letters only; words are distinct.
Hint 1

Insert every word into a trie; then start a depth-first search from each cell, moving down the trie as you step.

Hint 2

Stop exploring as soon as the current path is not a prefix in the trie.

Hint 3

Clear a word from the trie once found so it is reported only once.

Discussion 0

Join free to post in the discussion.

Good practice for: Game Developer, Frontend Developer, Mobile App Developer, Backend Developer, AI Engineer (LLM & Generative AI)

Run checks your code on 2 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.