LeetCode: Add and Search Word C#

Question

This is a Leetcode problem:

Design a data structure that supports the following two operations:

• void addWord(word)
• bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad") 
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true 
search("b..") -> true

Note:

You may assume that all words consist of lowercase letters a - z.

Here is my solution to this challenge:

using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace TrieQuestions
{
 /// <summary>
 /// https://leetcode.com/explore/learn/card/trie/148/practical-application-i/1052/
 /// </summary>
 [TestClass]
 public class WordDictionaryTest
 {
 [TestMethod]
 public void AddWordTest()
 {
 WordDictionary wordDic = new WordDictionary();
 wordDic.AddWord("cat");
 Assert.IsTrue(wordDic.Search("cat"));
 }
 [TestMethod]
 public void SearchWordDoT()
 {
 WordDictionary wordDic = new WordDictionary();
 wordDic.AddWord("cat");
 Assert.IsTrue(wordDic.Search("c.t"));
 }
 [TestMethod]
 public void SearchWordOne()
 {
 WordDictionary wordDic = new WordDictionary();
 wordDic.AddWord("a");
 Assert.IsTrue(wordDic.Search("."));
 }
 [TestMethod]
 public void LeetCodeTest()
 {
 WordDictionary wordDic = new WordDictionary();
 wordDic.AddWord("bad");
 wordDic.AddWord("dad");
 wordDic.AddWord("mad");
 Assert.IsFalse(wordDic.Search("pad"));
 Assert.IsTrue(wordDic.Search("bad"));
 Assert.IsTrue(wordDic.Search(".ad"));
 Assert.IsTrue(wordDic.Search("b.."));
 }
 [TestMethod]
 public void LeetCodeTest2()
 {
 WordDictionary wordDic = new WordDictionary();
 wordDic.AddWord("at");
 wordDic.AddWord("and");
 wordDic.AddWord("an");
 wordDic.AddWord("add");
 Assert.IsFalse(wordDic.Search("a"));
 Assert.IsFalse(wordDic.Search(".at"));
 wordDic.AddWord("bat");
 Assert.IsTrue(wordDic.Search(".at"));
 Assert.IsTrue(wordDic.Search("an."));
 Assert.IsFalse(wordDic.Search("a.d."));
 Assert.IsFalse(wordDic.Search("b."));
 Assert.IsTrue(wordDic.Search("a.d"));
 Assert.IsFalse(wordDic.Search("."));
 }
 }
 public class WordDictionary
 {
 private TrieNode _head;
 /** Initialize your data structure here. */
 public WordDictionary()
 {
 _head = new TrieNode();
 }
 /** Adds a word into the data structure. */
 public void AddWord(string word)
 {
 var current = _head;
 foreach (var letter in word)
 {
 if (!current.Edges.TryGetValue(letter, out var output))
 {
 output = current.Edges[letter] = new TrieNode();
 }
 current = output;
 }
 current.IsTerminal = true;
 }
 /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
 public bool Search(string word)
 {
 return Match(word, 0, _head);
 }
 private bool Match(string word, int i, TrieNode node)
 {
 if (i == word.Length)
 {
 return node.IsTerminal;
 }
 //if this is a regular letter check if it exists and mode on to the next letter
 if (word[i] != '.')
 {
 if (!node.Edges.ContainsKey(word[i]))
 {
 return false;
 }
 else
 {
 return Match(word, i + 1, node.Edges[word[i]]);
 }
 }
 else
 {
 //if we get a . try all of the different letters in recursion
 // if one of them returns true return true, there is a valid path to the next letter
 foreach (var currentNode in node.Edges)
 {
 if (Match(word, i + 1, currentNode.Value))
 {
 return true;
 }
 }
 }
 return false;
 }
 }
 /**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.AddWord(word);
 * bool param_2 = obj.Search(word);
 */
}

Please review my design and performance.

• Brad M: You should reuse the value of word[i]
• Ben A: There is a Meta CR question involving this post

Answer 1

Short review: not a whole lot to say. I don't think breaking any of the method up any further would really help matters, and none of them should be combined, so the overall design looks reasonable to me.

Documentation

I'm guessing the comments next to the methods are provided by the website: you should add proper inline documentation. Even if you are (for some reason) imposing a time limit on how long you spend designing and writing these programs, you should still go to the effort of documenting the API clearly, because it is a valuable skill itself. However, it's often a good idea to write the documentation before even implementing a method or class, so that you are forced to express precisely what it is to do (not how it will do it).

Naming

I'm not overly fond of the name output in this line:

if (!current.Edges.TryGetValue(letter, out var output))

Output suggests it is outputted: it is outputted by TryGetValue, but that's TryGetValue's problem: your problem is finding a descendent/child node.

currentNode is also a bit confusing: node is the 'current node', currentNode is a KeyValuePair. You might want to call it child and enumerate node.Edges.Values, since you don't need the keys.

I'm not sold on the name Edges either, since it isn't an arbitrary directed graph.

Misc

• The spec says nothing about how to handle invalid data, but both Match and AddWord will throw a mysterious NullReferenceException when confronted with a null: much better to check throw a helpful ArgumentNullException.

• You might consider making _head readonly, which expresses the intention that it isn't going to change and prevents someone violating this assumption in the future.

• You might consider making Match static, since it doesn't need access to any state, which would make it easier to maintain because it will be easier to understand and harder to break.

• This comment is misleading: // if one of them returns true return true, there is a valid path to the next letter