Citadel phone screen

Implement Trie and it's supporting functions -

* insert(word) - Insert a word in the trie,


search(word) - search if the word exists in the trie, and
startsWith(prefix) - search if there exist any word which starts with <prefix>.

Clarified if we are only dealing with lowercase alphabets. Yes.

I implemented

TrieNode

like below.

class TrieNode{
int val;
vector<TrieNode*> children;
};

Follow up question.
Currently, we are occupying 26 space for children. How can we optimize it ?
Suggested to use a Map instead of vector.

class TrieNode{
int val;
unordered_map<int, TrieNode*> child;
};

// int denotes 0 for 'a', 1 for 'b', or you can do char too in this case.
// I chose int.

Looks good.

Bonus question.

Implement

longestPrefixWhichStartsWithPrefix(prefix) - find the longest prefix which starts with a given prefix.

prefix = abc
words = [abcdef, abcdeg] -> abcde

Cleared the round.