Design a Word Filter (Prefix/Suffix Search)

To solve the Word Filter problem efficiently, I would first clarify if we need exact matches or partial overlaps, assuming standard exact matching for now. A naive approach checking every word against both prefix and suffix takes O(N * L) per query, which is too slow for large datasets like Uber's ride history. Instead, I propose building two specialized Tries: one storing all words reversed for suffix lookups, and another storing words normally for prefix lookups. However, since we need the same word index for both, a more elegant solution involves a single Trie where each node stores a list of word indices that pass through it. When inserting 'apple', we add 'apple' to the prefix path and 'elppa' to the suffix path, tagging each node with the index. For a query like prefix='ap', suffix='le', we traverse the prefix trie to find nodes containing 'ap', then the suffix trie for 'le', and return the intersection of their stored index lists. This reduces search time to O(L) where L is word length, independent of the total number of words. While this increases space complexity due to redundant storage, it drastically improves query performance, which aligns with Uber's need for low-latency responses in real-time navigation and search features.