Trie: effective algorithm for searching dictionary

Trie is so call "prefix tree".

In addition, prefix is like the followings.

For example,

String = "abcdef"

1st prefix substring is "abcdef"
2nd prefix substring is "abcde"
3rd prefix substring is "abcd"
....

....

So, all substring of prefix was represented to a tree.

Trie is made from the concept of prefix tree and all nodes of trie don't have any character but all node can have one index.

This example is for S = {"to", "tea", "ted", "ten", "A", "i", "in", "inn"} and the index of all elements of S = {7, 3, 4, 12, 15, 11, 5, 9}

The searching time of trie is very fast, and by the deep first search (DFS), the time complexity is O(m), in case of a string whose length is m.

Cited from Wikipedia

Trie is very available to search dictionary words. Because the sort of dictionary is very similar with trie.