Leetcode discuss: 208. Implement Trie (Prefix Tree)

Here is the post.

C# Trie algorithm practice in June 2020

June 24, 2020

Introduction

It is the second algorithm of my mock interview. I did not start to work on until 20 minutes left. So I did successfully submit the answer, since I just worked on Trie algorithm hard level 212 Word search. I also wrote in detail how to design a Trie. The link will be provided here as well.

Here are my practice:

1. Understand Trie recursive data structure of Tree;
2. Think about Trie as a binary tree when I implement, and then understand "new Trie()" for child node assignment;
3. Do not get confused with statement "root.word != null", another one is "word != null"

public class Trie {

    
    private Trie[] Children = new Trie[26];
    private string word; 
    
    /** Initialize your data structure here. */
    public Trie() {
        //Children = new Trie[26];
        
    }
    
    /** Inserts a word into the trie. */
    public void Insert(string word) {
        if(word == null || word.Length == 0)
            return;
        
        var root = this; 
        
        foreach(var item in word)
        {
            if(root.Children[item - 'a'] == null)
            {
                root.Children[item - 'a'] = new Trie();
            }
            
            root = root.Children[item - 'a'];
        }
        
        root.word = word;  
    }
    
    /** Returns if the word is in the trie. */
    public bool Search(string word) {
        if(word == null || word.Length == 0)
            return false;
        
        var root = this; 
        
        foreach(var item in word)
        {
            if(root.Children[item - 'a'] == null)
            {
                return false;
            }
            
            root = root.Children[item - 'a'];
        }
        
        return root.word != null; 
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public bool StartsWith(string prefix) {
        if(prefix == null || prefix.Length == 0)
            return false;
        
        var root = this; 
        
        foreach(var item in prefix)
        {
            if(root.Children[item - 'a'] == null)
            {
                return false;
            }
            
            root = root.Children[item - 'a'];
        }
        
        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);
 */