Problem of The Day: Implement Trie (Prefix Tree)

Problem Statement

leetcode problem link

My Solution [Accepted]

public class TrieNode {
    public bool IsWord { set; get; }
    public Dictionary<char, TrieNode> Children { set; get;} = new ();
}

public class Trie {
    private TrieNode _root;

    public Trie() {
        _root = new ();
    }

    public void Insert(string word) {
        var curr = _root;
        foreach(var c in word) {
            if (!curr.Children.ContainsKey(c)) {
                curr.Children[c] = new TrieNode();
            }
            curr = curr.Children[c];
        }
        curr.IsWord = true;
    }

    public bool Search(string word) {
        var curr = _root;
        foreach (var c in word) {
            if (!curr.Children.ContainsKey(c)) return false;
            curr = curr.Children[c];
        }

        return curr.IsWord;
    }

    public bool StartsWith(string prefix) {
        var curr = _root;
        foreach (var c in prefix) {
            if (!curr.Children.ContainsKey(c)) return false;
            curr = curr.Children[c];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.Insert(word);
 * bool param_2 = obj.Search(word);
 * bool param_3 = obj.StartsWith(prefix);
 */

Editorial

class TrieNode:
    def __init__(self):
        # Initialize links array and isEnd flag
        self.links = [None] * 26
        self.is_end = False

    def contains_key(self, ch: str) -> bool:
        return self.links[ord(ch) - ord('a')] is not None

    def get(self, ch: str) -> 'TrieNode':
        return self.links[ord(ch) - ord('a')]

    def put(self, ch: str, node: 'TrieNode') -> None:
        self.links[ord(ch) - ord('a')] = node

    def set_end(self) -> None:
        self.is_end = True

    def is_end(self) -> bool:
        return self.is_end


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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if not node.contains_key(ch):
                node.put(ch, TrieNode())
            node = node.get(ch)
        node.set_end()

    def search_prefix(self, word: str) -> TrieNode:
        node = self.root
        for ch in word:
            if node.contains_key(ch):
                node = node.get(ch)
            else:
                return None
        return node

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

    def starts_with(self, prefix: str) -> bool:
        node = self._search_prefix(prefix)
        return node is not None