Word Search II
Given a letter grid and a list of words, return every word that can be traced through adjacent cells without reusing a cell.
A way to picture it
It's a word-search puzzle with a whole list of words. Instead of hunting for each word separately, you carry one pocket dictionary shaped like a letter tree. As your finger slides across the grid, the dictionary tells you instantly whether any word could still continue that way.
How to approach it
Build a trie of the words, then DFS from every cell, moving through the trie in step. Abandon a path the moment the trie has no matching child.
Example
Input: {"board":[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],"words":["oath","pea","eat","rain"]}. Output: ["eat","oath"].
Complexity: O(cells · 4 · 3^(L−1)) time and O(total letters) space. Each DFS branches to at most 3 unvisited neighbours; the trie prunes most paths early.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.