Given an m x n board of characters and a list of words, find all words on the board. Each word must be formed from letters of sequentially adjacent cells (horizontally or vertically), and the same cell may not be used more than once per word.
For example, given board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]] and words = ["oath","pea","eat","rain"], the output is ["eat","oath"].
Explain your approach and state the time and space complexity.
How to approach it
- Hint 1
Searching each word individually with DFS would be slow. Think about how to search for all words simultaneously.
- Hint 2
Build a trie from the word list. Then run DFS from each cell on the board, following the trie to prune invalid paths.
- Hint 3
During DFS, if the current trie node has no children matching the next cell, stop exploring. If you reach an end-of-word node, add that word to results.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.