Clever Geek Handbook

Trie structure for a word with subwords

What is the structure of the trie for words with subwords like "icecream" (contains "i", "ice", "cream", "icecream"); "businessman" (contains "bus", "is", "business", "person", "businessman").

I know how it will be for those who do not have subwords like "inn", but I am confused about the above words.

Thanks in advance.

+3


source to share


1 answer


In your trie node, you can simply have a boolean "isTerminal" to indicate if the word ends with this node. Thus, all the words "bus", "business" and "businessman" begin with node 'b' and follow the same path. Nodes in 's' for 'bus', 's' for 'business' and 'n' for 'business' will have isTerminal = true.

Although "person" is contained in "businessman", it should be viewed as a word starting with "m" child node from root and in a separate path.



Therefore, all words begin strictly from the upper literal nodes (children from the root) and end at different levels, indicated by the boolean value isTerminal = true.

+4


source






More articles:


All Articles