Search Engine - Amazon Top Interview Questions

                        Solution in C++ :

struct Node {
    bool end = false;
    Node* next[26] = {0};
};
class SearchEngine {
    public:
    SearchEngine() {
    }

    void add(string word) {
        Node* cur = &head;
        for (char c : word) {
            if (!cur->next[c - 'a']) cur->next[c - 'a'] = new Node();
            cur = cur->next[c - 'a'];
        }
        cur->end = true;
    }

    bool exists(string word) {
        return internal_search(word, 0, &head);
    }

    private:
    bool internal_search(string& word, int idx, Node* node) {
        if (idx >= word.size()) return node->end;
        if (word[idx] == '.') {
            for (char c = 'a'; c <= 'z'; c++) {
                word[idx] = c;
                if (internal_search(word, idx, node)) return true;
            }
            word[idx] = '.';
        } else {
            Node* next_node = node->next[word[idx] - 'a'];
            if (next_node)
                return internal_search(word, idx + 1, next_node);
            else
                return false;
        }
        return false;
    }
    Node head;
};
                    

                        Solution in Python : 
                            
class SearchEngine:
    def __init__(self):
        self.trie = [False, {}]
        # Example format
        # [False, { 'd': [True, { 'o': [True, {} ] } ]] }

    def add(self, word):
        curr = self.trie
        for i in range(len(word)):
            if word[i] not in curr[1]:
                # Add entry to trie if doesn't exist
                curr[1][word[i]] = [False, {}]
            curr = curr[1][word[i]]
        # Designate the current position as an ending/terminating node
        curr[0] = True

    def exists(self, word):
        def helper(word, trie):
            curr = trie
            for i in range(len(word)):
                if word[i] in curr[1]:
                    # Follow child node if the character exists
                    curr = curr[1][word[i]]
                elif word[i] == ".":
                    # Traverse over all children if wildcard is found
                    for k in curr[1]:
                        if helper(word[i + 1 :], curr[1][k]):
                            return True
                    return False
                else:
                    # Current character is not in our trie, so DNE
                    return False
            # If we reach the end, we need to check if this is an ending node
            return curr[0]

        return helper(word, self.trie)