the problem is not efficiency, its relevancy. Say you have a result "hacker news". If its a pure prefix trie, this wont match the query "news", even though you

the problem is not efficiency, its relevancy. Say you have a result "hacker news". If its a pure prefix trie, this wont match the query "news", even though you probably want to return this as a suggestion. My hack around this would be to add both "hacker news" and "news" in the trie-Its still not perfect, since it wouldn't match "acker" or "ws" etc.