Trie

#include <bits/stdc++.h>

using namespace std;

class Trie {

public:

    bool isleaf;

    unordered_map <char, Trie *> childrenTrie;

    /** Initialize your data structure here. */

    Trie() {

        isleaf = false;

    }

    /** Inserts a word into the trie. */

    void insert(string word) {

        Trie * curr = this;

        for(char ch:word)

        {

            if(curr->childrenTrie.find(ch) == curr->childrenTrie.end())

                curr->childrenTrie[ch] = new Trie();

            curr = curr->childrenTrie[ch];

        }

        curr->isleaf = true;

    }

    /** Returns if the word is in the trie. */

    bool search(string word) {

        Trie * curr = this;

        for(char ch:word)

        {

            if(curr->childrenTrie.find(ch) != curr->childrenTrie.end())

                curr= curr->childrenTrie[ch];

            else

            {return false;}

        }

        return curr->isleaf;

    }

    /** Returns if there is any word in the trie that starts with the given prefix. */

    bool startsWith(string prefix) {

        Trie * curr = this;

        for(char ch:prefix)

        {

            if(curr->childrenTrie.find(ch) != curr->childrenTrie.end())

                curr = curr->childrenTrie[ch];

            else

                return false;

        }

        return true;

    }

    /** find the longest common prefix */

    string findlcp()

    {

        string lcp;

        Trie* curr = this;

        // do till we find a leaf node or node has more than 1 children

        while (curr && !curr->isleaf && (curr->childrenTrie.size() == 1))

        {

            // get iterator to only child

            auto it = curr->childrenTrie.begin();

            // append current char to LCP

            lcp += it->first;

            // update curr pointer to child node

            curr = it->second;

        }

        return lcp;

    }

};

int main()

{

    cout<<"Start to test the trie tree..."<<endl;

    Trie obj = Trie();

    obj.insert("myotest");

    obj.insert("myobject");

    obj.insert("myok");

    bool hasit = obj.search("mytest");

    bool ok = obj.startsWith("a");

    cout<<hasit<<","<<ok<<endl;

    cout<<obj.findlcp()<<endl;

    return 0;

}