 # 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;
}``````