Implement Trie

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

    void insert(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) {
        Node* n = find(word);
        return n && n->isEnd;
    }

    bool startsWith(const string& prefix) {
        return find(prefix) != nullptr;
    }
private:
    Node* find(const string& s) {
        Node* cur = root;
        for (char c : s) {
            int i = c - 'a';
            if (!cur->child[i]) return nullptr;
            cur = cur->child[i];
        }
        return cur;
    }
};

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

func Constructor() Trie {
    return Trie{}
}

func (t *Trie) Insert(word string) {
    cur := t
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.child[idx] == nil {
            cur.child[idx] = &Trie{}
        }
        cur = cur.child[idx]
    }
    cur.isEnd = true
}

func (t *Trie) find(s string) *Trie {
    cur := t
    for i := 0; i < len(s); i++ {
        idx := s[i] - 'a'
        if cur.child[idx] == nil {
            return nil
        }
        cur = cur.child[idx]
    }
    return cur
}

func (t *Trie) Search(word string) bool {
    n := t.find(word)
    return n != nil && n.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.find(prefix) != nil
}

from typing import Optional

class Trie:
    def __init__(self):
        self.children: list = [None] * 26
        self.is_end = False

    def insert(self, word: str) -> None:
        cur = self
        for ch in word:
            i = ord(ch) - ord('a')
            if cur.children[i] is None:
                cur.children[i] = Trie()
            cur = cur.children[i]
        cur.is_end = True

    def _find(self, s: str) -> Optional['Trie']:
        cur = self
        for ch in s:
            i = ord(ch) - ord('a')
            if cur.children[i] is None:
                return None
            cur = cur.children[i]
        return cur

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

class TrieNode {
    constructor() {
        this.children = new Array(26).fill(null);
        this.isEnd = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let cur = this.root;
        for (const ch of word) {
            const i = ch.charCodeAt(0) - 97;
            if (!cur.children[i]) cur.children[i] = new TrieNode();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }

    _find(s) {
        let cur = this.root;
        for (const ch of s) {
            const i = ch.charCodeAt(0) - 97;
            if (!cur.children[i]) return null;
            cur = cur.children[i];
        }
        return cur;
    }

    search(word) {
        const node = this._find(word);
        return node !== null && node.isEnd;
    }

    startsWith(prefix) {
        return this._find(prefix) !== null;
    }
}

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

class Trie {
    private TrieNode root;

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

    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new TrieNode();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }

    private TrieNode find(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) return null;
            cur = cur.children[i];
        }
        return cur;
    }

    public boolean search(String word) {
        TrieNode n = find(word);
        return n != null && n.isEnd;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }
}

class TrieNode {
    children: (TrieNode | null)[] = new Array(26).fill(null);
    isEnd: boolean = false;
}

class Trie {
    private root: TrieNode = new TrieNode();

    insert(word: string): void {
        let cur: TrieNode = this.root;
        for (const ch of word) {
            const i = ch.charCodeAt(0) - 97;
            if (!cur.children[i]) cur.children[i] = new TrieNode();
            cur = cur.children[i]!;
        }
        cur.isEnd = true;
    }

    private find(s: string): TrieNode | null {
        let cur: TrieNode | null = this.root;
        for (const ch of s) {
            const i = ch.charCodeAt(0) - 97;
            if (!cur!.children[i]) return null;
            cur = cur!.children[i];
        }
        return cur;
    }

    search(word: string): boolean {
        const node = this.find(word);
        return node !== null && node.isEnd;
    }

    startsWith(prefix: string): boolean {
        return this.find(prefix) !== null;
    }
}