#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>


class Trie
{
    struct Node {
        bool end_node = false;
        std::unordered_map<char, Node*> children;
    };

private:
    void remove_trie(Node* node) 
    {
        for (auto [_, child] : node->children) {
            remove_trie(child);
        }
        delete node;
    }

public:
    Trie() : m_trie(new Node()) { }

    void insert(const std::string &key)
    {
        auto trie = m_trie;

        for (auto c : key) {
            if (trie->children.find(c) == trie->children.end()) {
                trie->children[c] = new Node();
            }
            trie = trie->children[c];
        }

        trie->end_node = true;
    }

    bool find(const std::string &key) 
    {
        auto trie = m_trie;

        for (auto c : key) {
            if (trie->children.find(c) == trie->children.end()) {
                return false;
            }
            trie = trie->children[c];
        }

        return trie->end_node;
    }

    std::string prefix()
    {
        auto trie = m_trie;

        std::string str;

        while (trie->children.size() == 1) {
            auto [c, child] = *trie->children.begin();

            str.push_back(c);
            trie = child;
        }

        return str;
    }

    ~Trie()
    {
        remove_trie(m_trie);
    }

private:
    Node *m_trie;
};


int main(void)
{
    std::vector<std::string> words = { "cod", "coder", "coding", "codecs" };

    auto trie = new Trie();

    for (auto word : words) {
        trie->insert(word);
    }

    std::cout << std::boolalpha << trie->find("codingsa") << std::endl;

    std::cout << trie->prefix() << std::endl;

    delete trie;

    return 0;
}