Trie-Trie-Trie!!!

Leetcode is obsessed with Tries. It is indeed a useful data structure, and someone fun to implement with a hashtable and recursion. Here is their latest: Implement Trie II (Prefix Tree) - LeetCode

1804. Implement Trie II (Prefix Tree)

Medium

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• int countWordsEqualTo(String word) Returns the number of instances of the string word in the trie.
• int countWordsStartingWith(String prefix) Returns the number of strings in the trie that have the string prefix as a prefix.
• void erase(String word) Erases the string word from the trie.

 

Example 1:

Input
["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"]
[[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]]
Output
[null, null, null, 2, 2, null, 1, 1, null, 0]

Explanation
Trie trie = new Trie();
trie.insert("apple");               // Inserts "apple".
trie.insert("apple");               // Inserts another "apple".
trie.countWordsEqualTo("apple");    // There are two instances of "apple" so return 2.
trie.countWordsStartingWith("app"); // "app" is a prefix of "apple" so return 2.
trie.erase("apple");                // Erases one "apple".
trie.countWordsEqualTo("apple");    // Now there is only one instance of "apple" so return 1.
trie.countWordsStartingWith("app"); // return 1
trie.erase("apple");                // Erases "apple". Now the trie is empty.
trie.countWordsStartingWith("app"); // return 0

 

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, countWordsEqualTo, countWordsStartingWith, and erase.
• It is guaranteed that for any function call to erase, the string word will exist in the trie.

The most complicated part of this solution is to count all the prefixes. That requires, in my case:

1/ A function inside the class that takes as input an instance of the class itself

2/ A full DFS to account for all the prefixes

Code is below, cheers, ACC

public class Trie
{
    private Hashtable children = null;
    private int numberInstances = 0;
    public Trie()
    {
        children = new Hashtable();
        numberInstances = 0;
    }

    public void Insert(string word)
    {
        if (String.IsNullOrEmpty(word))
        {
            numberInstances++;
            return;
        }

        if (!children.ContainsKey(word[0])) children.Add(word[0], new Trie());
        Trie child = (Trie)children[word[0]];
        child.Insert(word.Substring(1));
    }

    public int CountWordsEqualTo(string word)
    {
        if (String.IsNullOrEmpty(word)) return numberInstances;

        if (!children.ContainsKey(word[0])) return 0;
        Trie child = (Trie)children[word[0]];
        return child.CountWordsEqualTo(word.Substring(1));
    }

    public int CountWordsStartingWith(string prefix)
    {
        if (String.IsNullOrEmpty(prefix)) return CountAll(this);

        if (!children.ContainsKey(prefix[0])) return 0;
        Trie child = (Trie)children[prefix[0]];
        return child.CountWordsStartingWith(prefix.Substring(1));
    }

    private int CountAll(Trie trie)
    {
        if (trie == null) return 0;
        int result = trie.numberInstances;

        if (trie.children != null)
        {
            foreach (char c in trie.children.Keys)
            {
                Trie child = (Trie)trie.children[c];
                result += CountAll(child);
            }
        }

        return result;
    }

    public void Erase(string word)
    {
        if (String.IsNullOrEmpty(word))
        {
            if(numberInstances > 0) numberInstances--;
            return;
        }

        if (!children.ContainsKey(word[0])) return;
        Trie child = (Trie)children[word[0]];
        child.Erase(word.Substring(1));
    }
}