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


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

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

    void add(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() 
    {
        std::string str;

        auto trie = m_trie;

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

            str += c;
            trie = node;

            if (trie->end_node) {
                break;
            }
        }

        return str;
    }

    ~Trie() 
    {
        for (auto [_, node] : m_trie->children) {
            delete node;
        }
    }

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->add(word);
    }

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

    delete trie;
    
    return 0;
}