Tag: String search

A trie is a N-ary tree data structure for storing strings in order to support fast string search. Tries can insert or search the string in O(L) time where L is length of string. Trie is mainly used in cases where dictionary kind of data structure needs to be maintained.

Assuming the dictionary contains all the strings were made of all small alphabets “a” to “z” then each node of the trie will have 26 pointers, one for each character. Let’s have a look into simple trie data structure definition.

#define LETTER_LENGTH 26
class Trie
{
    public:
        Trie* m_ptr[LETTER_LENGTH];
        bool is_word_complete;
        Trie ();
};
Trie::Trie ()
{
    for (int i = 0; i < LETTER_LENGTH; i++)
    {
        m_ptr[i] = NULL;
    }
}