taggit Summary
The advantage using Tries is that for prefixes such as ‘a’, ‘aa’, ‘aaa’, ‘aaaa’ and ‘aaaaa’, they are stored as separate words in the hash-set, but in the Trie they are stored as part of the same root to leaf path as all common prefixes share the same path in a Trie. For each word, compute its prefixes, if for any prefix, that prefix is present in the list of words then recursively check if the suffix is another word in the list or is also a concatenated word. Basically we store each word from the list in the Trie and then for each word we traverse the Trie to check whether the word is composed of 2 or more words from the list. The idea is that apart from storing the words in the Trie, we also store the count of words rooted at a node in the Trie i.e. number of suffixes starting at that node.