2
\$\begingroup\$

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>();
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ @wolfy no you can't. Why is it better? Maybe I can create a singleton or something close to it. \$\endgroup\$ – Gilad May 17 at 21:55
  • \$\begingroup\$ @Wolfy: C# is a managed language, so I'm not sure what you're getting at? \$\endgroup\$ – Pieter Witvoet May 17 at 23:33
  • \$\begingroup\$ @PieterWitvoet ahh okay then nevermind, sorry I never used C# before... \$\endgroup\$ – Wolfy May 17 at 23:35
6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot. I didn't notice those \$\endgroup\$ – Gilad May 18 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.