Key optimizations:
Store the word at end node: Instead of rebuilding the path string, store the complete word at isEndOfWord nodes. Retrieve directly when found.
Remove found words from trie: After finding a word, remove its path from the trie. This prevents duplicate finds and prunes the trie for future searches.
Prune empty branches: If a node has no children after removing a word, delete it from its parent. This speeds up future traversals.
# In TrieNode, store the word itself
node.word = word # set during insert
# After finding
if node.word:
result.append(node.word)
node.word = None # mark as found
These optimizations can dramatically improve performance on large inputs.