Word Search II
The problem
Given a rectangular letter board and a list of distinct nonempty words, return those that can be traced using horizontal or vertical neighbors. A cell cannot be reused within one word.
Example
board = [["c", "a"], ["t", "r"]], words = ["car", "cat"] → ["car"]
Need a hint?
Share work between words with the same prefix.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Build a trie from the words, then start a backtracking search at each cell. Follow only edges that exist in the trie, temporarily mark each visited cell, and restore it on return. Record terminal words in a set or clear their terminal marker to avoid duplicate output.
Complexity
O(total word characters + mn·4·3^(L−1)) loose worst-case time for longest word L; O(total word characters + L) auxiliary space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.