Design Add and Search Words Data Structure

class WordDictionary {
    struct Node {
        Node* child[26]{};
        bool isEnd = false;
    };
    Node* root;
public:
    WordDictionary() : root(new Node()) {}

    void addWord(const string& word) {
        Node* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (!cur->child[i]) cur->child[i] = new Node();
            cur = cur->child[i];
        }
        cur->isEnd = true;
    }

    bool search(const string& word) {
        return dfs(root, word, 0);
    }
private:
    bool dfs(Node* node, const string& w, int idx) {
        if (!node) return false;
        if (idx == (int)w.size()) return node->isEnd;
        char c = w[idx];
        if (c == '.') {
            for (int i = 0; i < 26; ++i) {
                if (node->child[i] && dfs(node->child[i], w, idx + 1)) return true;
            }
            return false;
        }
        return dfs(node->child[c - 'a'], w, idx + 1);
    }
};

type trieNode struct {
    child [26]*trieNode
    isEnd bool
}

type WordDictionary struct {
    root *trieNode
}

func Constructor() WordDictionary {
    return WordDictionary{root: &trieNode{}}
}

func (wd *WordDictionary) AddWord(word string) {
    cur := wd.root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.child[idx] == nil {
            cur.child[idx] = &trieNode{}
        }
        cur = cur.child[idx]
    }
    cur.isEnd = true
}

func (wd *WordDictionary) Search(word string) bool {
    var dfs func(node *trieNode, idx int) bool
    dfs = func(node *trieNode, idx int) bool {
        if node == nil {
            return false
        }
        if idx == len(word) {
            return node.isEnd
        }
        c := word[idx]
        if c == '.' {
            for i := 0; i < 26; i++ {
                if node.child[i] != nil && dfs(node.child[i], idx+1) {
                    return true
                }
            }
            return false
        }
        return dfs(node.child[c-'a'], idx+1)
    }
    return dfs(wd.root, 0)
}

class WordDictionary:
    def __init__(self):
        self.root: dict = {}

    def addWord(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur:
                cur[c] = {}
            cur = cur[c]
        cur['$'] = True

    def search(self, word: str) -> bool:
        def dfs(node: dict, idx: int) -> bool:
            if idx == len(word):
                return node.get('$', False)
            c = word[idx]
            if c == '.':
                for k, child in node.items():
                    if k != '$' and dfs(child, idx + 1):
                        return True
                return False
            if c not in node:
                return False
            return dfs(node[c], idx + 1)

        return dfs(self.root, 0)

class WordDictionary {
    constructor() {
        this.root = {};
    }

    addWord(word) {
        let cur = this.root;
        for (const c of word) {
            if (!cur[c]) cur[c] = {};
            cur = cur[c];
        }
        cur.$ = true;
    }

    search(word) {
        const dfs = (node, idx) => {
            if (idx === word.length) return node.$ === true;
            const c = word[idx];
            if (c === '.') {
                for (const k of Object.keys(node)) {
                    if (k !== '$' && dfs(node[k], idx + 1)) return true;
                }
                return false;
            }
            if (!node[c]) return false;
            return dfs(node[c], idx + 1);
        };
        return dfs(this.root, 0);
    }
}

class TrieNode {
    TrieNode[] child = new TrieNode[26];
    boolean isEnd = false;
}

class WordDictionary {
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.child[idx] == null) cur.child[idx] = new TrieNode();
            cur = cur.child[idx];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    private boolean dfs(TrieNode node, String w, int idx) {
        if (node == null) return false;
        if (idx == w.length()) return node.isEnd;
        char c = w.charAt(idx);
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (node.child[i] != null && dfs(node.child[i], w, idx + 1)) return true;
            }
            return false;
        }
        return dfs(node.child[c - 'a'], w, idx + 1);
    }
}

class WordDictionary {
    private root: Record<string, any> = {};

    addWord(word: string): void {
        let cur: Record<string, any> = this.root;
        for (const c of word) {
            if (!cur[c]) cur[c] = {};
            cur = cur[c];
        }
        cur.$ = true;
    }

    search(word: string): boolean {
        const dfs = (node: Record<string, any>, idx: number): boolean => {
            if (idx === word.length) return node.$ === true;
            const c = word[idx];
            if (c === '.') {
                for (const k of Object.keys(node)) {
                    if (k !== '$' && dfs(node[k], idx + 1)) return true;
                }
                return false;
            }
            if (!node[c]) return false;
            return dfs(node[c], idx + 1);
        };
        return dfs(this.root, 0);
    }
}