Tries
Retrieval: when is a trie worth it?
Two problems rebuilt cold, plus the honest answer about when a set is better.
Key idea
Reach for a trie when
The question involves prefixes: does anything start with this, how many words share this beginning, what is the longest stored prefix of this string.
You are searching for many strings at once and want to fail fast on shared dead ends, which is the grid problem.
Lookup must not slow down as the dictionary grows, since a trie walk depends only on the query length.
Tip
And do not when
You only ever ask about exact membership. A set is shorter, faster in practice, and uses less memory.
The strings are long and share almost nothing. The trie degenerates to one node per character with no sharing, which is all the overhead and none of the benefit.
Building a trie because the problem mentions strings is a common overreach. The prefix question is the signal, not the data type.
Trie or set?
You must implement autocomplete: given a typed prefix, return every stored word beginning with it. Which structure, and why?
Implement Trie, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Word Search, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.