Trie Prefix Search

Implement a Trie (prefix tree) that supports inserting words and searching by full word or prefix.

Operations:

• Insert(word) — store the word in the trie
• Search(word) — return true if the word exists
• StartsWith(prefix) — return true if any word starts with the prefix

Function signature

type Trie struct { /* ... */ }

func NewTrie() *Trie
func (t *Trie) Insert(word string)
func (t *Trie) Search(word string) bool
func (t *Trie) StartsWith(prefix string) bool

Examples

Example 1:

Insert("apple")
Search("apple") -> true
Search("app") -> false
StartsWith("app") -> true
Insert("app")
Search("app") -> true

Constraints

• 1 <= word.length, prefix.length <= 30
• Words consist of lowercase letters a-z
• Up to 10^5 operations

Hints

1. Each node holds a map of children and an isWord flag.
2. Insert walks the trie, creating nodes as needed.
3. Search and StartsWith differ only at the end check.

Notes

• Trie is great for fast prefix queries and autocomplete.
• Memory usage is higher than hash sets but structured by prefixes.