O(nk) time and O(nk) space solution using


#1
struct TrieNode
{
    char id;
    int wordsEntryHere;
    unordered_map<char, TrieNode*> children;
    
    TrieNode(char id) : id(id)
    {
        wordsEntryHere = 0;
    }
};

struct Trie
{
    TrieNode *root;
    Trie() { root = new TrieNode('/'); }
    
    void insert(string word)
    {
        TrieNode *start = root;
        for (char c : word) {
            auto iter = start->children.find(c);
            if (iter != start->children.end())
                start = iter->second;
            else
                start = start->children[c] = new TrieNode(c);
            start->wordsEntryHere++;
        }
        //start->wordsCompletedHere++;
    }
};

// Say, abc is common prefix in abcpqr, abcijk, abcxyz
// Then for all three entries, trienode with a, b and c will have three entrycount
// Trienode with p will have entrycount = 1
// Trienode with i will have entrycount = 1
// Trienode with x will have entrycount = 1
// So, the first node at which entrycount != total number of unique words is the node
// before which we will have our desired prefix
// Time : O(nk) + O(k), n = size of input array, k = length of string
// Space : O(nk) for unordered_set and trie
string Solution::longestCommonPrefix(vector<string> &A)
{
    Trie trie;
    unordered_set uset(A.begin(), A.end());
    
    for (auto word : uset)
        trie.insert(word);
    
    string prefix;
    int count = uset.size();
    TrieNode *root = trie.root;
    TrieNode *prev = root, *cur = nullptr;
    while (true) {
        auto iter = prev->children.begin();
        if (iter == prev->children.end())
            break;
        cur = iter->second;
        if (cur->wordsEntryHere != count)
            break;
        prefix += cur->id;
        prev = cur;
    }
    
    return prefix;
}