LeetCode: Trie Tree implementation, Search, Insert, startWith C#

Question

https://leetcode.com/problems/implement-trie-prefix-tree/

Please comment about performance and style.

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true 

Note:

You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings.

using System.Collections.Generic; using Microsoft.VisualStudio.TestTools.UnitTesting; namespace TrieQuestions { /// <summary> /// https://leetcode.com/problems/implement-trie-prefix-tree/ /// </summary> [TestClass] public class TrieTreeImplementation { [TestMethod] public void TrieInsertTest() { Trie trie = new Trie(); trie.Insert("cat"); Assert.IsTrue(trie.Search("cat")); } [TestMethod] public void TriePrefixSearchTest() { Trie trie = new Trie(); trie.Insert("cats"); Assert.IsTrue(trie.StartsWith("cat")); } [TestMethod] public void OneLetterEdgeCaseTest() { Trie trie = new Trie(); trie.Insert("a"); Assert.IsTrue(trie.Search("a")); Assert.IsTrue(trie.StartsWith("a")); } } public class Trie { public TrieNode Head { get; set; } /** Initialize your data structure here. */ public Trie() { Head = new TrieNode(); } /** Inserts a word into the trie. */ public void Insert(string word) { var current = Head; for (int i = 0; i < word.Length; i++) { if (!current.Edges.ContainsKey(word[i])) { current.Edges.Add(word[i], new TrieNode()); } current = current.Edges[word[i]]; } current.IsTerminal = true; } /** Returns if the word is in the trie. */ public bool Search(string word) { var current = Head; for (int i = 0; i < word.Length; i++) { if (!current.Edges.ContainsKey(word[i])) { return false; } current = current.Edges[word[i]]; } return current.IsTerminal == true; } /** Returns if there is any word in the trie that starts with the given prefix. */ public bool StartsWith(string prefix) { var current = Head; for (int i = 0; i < prefix.Length; i++) { if (!current.Edges.ContainsKey(prefix[i])) { return false; } current = current.Edges[prefix[i]]; } return true; } } public class TrieNode { public Dictionary<char, TrieNode> Edges { get; set; } public bool IsTerminal { get; set; } public TrieNode() { Edges = new Dictionary<char, TrieNode>(); } } } 

Answer 1

In terms of data structures and algorithms this all looks pretty straightforward - not much to say about that.

Performance

• Edges.ContainsKey and Edges[...] each perform a lookup. Edges.TryGetValue lets you achieve the same with just a single lookup.

Design

• I see no reason why Trie.Head should be public, and certainly not why it should have a public setter. That's poor encapsulation. Likewise, TrieNode.Edges should be get-only: you don't want outside code to be able to do Edges = null;.
• Search and StartsWith do exactly the same thing, except for the final check. I'd move the duplicate code to a TrieNode FindNode(string prefix) helper method.
• TrieNode is only used internally within Trie, so it makes sense to make it a private inner class.

Other notes

• You can remove Trie's constructor if you initialize Head directly: TrieNode Head { get; } = new TrieNode();. The same goes for TrieNode and Edges.
• I'd replace those for loops with foreach loops, for clarity's sake.
• Comparing a boolean against true is unnecessary. Just do return current.IsTerminal;
• I'd replace those default LeetCode comments with C#-specific xml comments.