Trie - Amazon Top Interview Questions

                        Solution in C++ :

class Trie {  // Time: O(L) for every operation, where L is the length of the input string
    private:
    bool is_word;
    Trie* children[26];

    public:
    Trie() {  // Constructor
        is_word = false;
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }

    ~Trie() {  // Destructor
        for (int i = 0; i < 26; i++)
            if (children[i]) delete children[i];  // Release children nodes
    }

    Trie* search(string& word) {
        Trie* node = this;
        for (char c : word) {
            if (node->children[c - 'a'] == nullptr) return nullptr;

            node = node->children[c - 'a'];
        }

        return node;
    }

    void add(string s) {
        Trie* node = this;
        for (char c : s) {
            if (node->children[c - 'a'] == nullptr) node->children[c - 'a'] = new Trie();

            node = node->children[c - 'a'];
        }

        node->is_word = true;
    }

    bool exists(string word) {
        Trie* node = search(word);
        return (node != nullptr) && (node->is_word);
    }

    bool startswith(string p) {
        Trie* node = search(p);
        return node != nullptr;
    }
};
                    

                        Solution in Python : 
                            
class Node:
    def __init__(self):
        self.children = defaultdict(Node)
        self.end = False


class Trie:
    def __init__(self):
        self.root = Node()

    def add(self, s):
        """We simply iterate through the word and add each character
        one by one. since we are using a defaultdict, we don't need
        to worry about creating a new node if a child doesn't exist

        In the end we set the `end` flag of the current node to true
        """
        cur = self.root
        for c in s:
            cur = cur.children[c]
        cur.end = True

    def exists(self, word):
        """
        We go by each character and see if the current node has a child
        mapped to that character. if it doesn't, return false. else keep
        going down. In the end check if the node's end flag is set to true
        """
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.end

    def startswith(self, p):
        """
        We go by each character and see if the current node has a child
        mapped to that character. if it doesn't, return false. else keep
        going down. we just return true without checking the end flag
        """
        cur = self.root
        for c in p:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True