The Runtime Theory
hardLeetCode#trie#dfs#pruning

Word Search II

Find all dictionary words that can be formed by nonrepeating adjacent cells in a character grid.

The Runtime Theory Team25 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

inboard=[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words=["oath","pea","eat","rain"]

out["eat","oath"]

inboard=[["a"]], words=["a"]

out["a"]

inboard=[["a","b"]], words=["ab","ba"]

out["ab","ba"]

Find all dictionary words that can be formed by nonrepeating adjacent cells in a character grid.

A good solution should

  • State the invariant or decision rule that makes the approach correct.
  • Explain the time and space complexity in terms of the input sizes and required output.
  • Handle empty, minimal, duplicate, and boundary-shaped inputs covered by the contract.

Reasoning prompt

Build one trie for the dictionary so shared prefixes are explored once. Prune exhausted trie branches and prevent reuse of a board cell.

Use the linked judge for the canonical problem. The examples above are compact TRT checks; write additional cases before submitting, especially for the boundary that tends to break your chosen invariant.

More practice in this topic

medium · triesDesign Add and Search Words Data Structuremedium · triesImplement Trie Prefix Tree

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save