Trie

Stores strings by sharing their common prefixes, so "car", "cart" and "card" walk the same first three nodes. Lookup costs one step per character regardless of how many words are stored — the property that makes tries the natural structure for autocomplete and routing tables.

Best

O(m)

Average

O(m)

Worst

O(m)

Space

O(ALPHABET · N · m)