1
\$\begingroup\$

This is a classic problem with a classic solution and I've seen it a number of times on this site, but I wanted to know what people thought of this C# implementation, as opposed to the numerous C implementations.

Below you'll find the source code, the output of the code and then a link to repl.it, so you can run the code in your browser.

Source code

using System;
using System.Collections.Generic;
using System.Linq;

class MainClass {
    // An array of valid words. Would normally contain way more words.
    private static string[] dictArray = new string[] {
        "trainee",
        "train"
    };

    public static void Main (string[] args) {
        Node dictTrie = CreateDictTrie(dictArray);
        Console.WriteLine(IsWord("Train", dictTrie)); // True
        Console.WriteLine(IsWord("Traine", dictTrie)); // False
        Console.WriteLine(IsWord("Trainee", dictTrie)); // True
    }

    // Create the trie to use for spell checking, based on an array of valid words.
    private static Node CreateDictTrie(string[] dictArray) {
        Node root = new Node();
        for (int i = 0; i < dictArray.Length; i++) {
            string word = dictArray[i];
            Node node = root;
            for (int j = 0; j < word.Length; j++) {
                char character = word[j];
                if (!node.Children.ContainsKey(character)) {
                    node.Children[character] = new Node();
                }
                node = node.Children[character];
            }
            node.IsWord = true;

        }
        return root;
    }

    // Check whether a string is a valid word.
    private static bool IsWord(string word, Node dictTrie) {
        word = word.ToLower();
        Node node = dictTrie;
        for (int i = 0; i < word.Length; i++) {
            char character = word[i];
            if (!node.Children.ContainsKey(character)) {
                return false;
            }
            node = node.Children[character];
        }
        return node.IsWord;
    }
}

// Class used for the trie structure.
public class Node {
    public bool IsWord;
    public Dictionary<char, Node> Children { get; set; }

    public Node() {
        Children = new Dictionary<char, Node>();
    }
}

Output

True
False
True

Repl.it link

https://repl.it/EOlt/14

I tried to make the code pretty readable, so if you wanted to really optimize the code, you could probably remove a few of the variable declarations and so on. But other than that, are there any overall performance problems with my approach? Anything else you think I could have done better? Feedback is much appreciated. Thanks!

Edit: I updated the code to use arrays and for loops instead of Lists and foreach loops, which should improve the performance a bit.

\$\endgroup\$
1
\$\begingroup\$

The trie creation could by very pretty if you made it an extension then can call it on the array:

var trie = new string[] 
{
    "trainee",
    "train",
    "tree"
}
.ToTrie();

The method itself can be simplified. You can use foreach to get rid of the indexes (unless performance really, really, really matters).

Sometimes it's also prettier to use the TryGetValue + else where you can assign all values in a single line to avoid duplication like:

    currentNode.Children[character] = new Node();     
}
currentNode = currentNode.Children[character];

To my taste it doesn't look nice. Instead I suggest this where I also use currentNode instead of just node which I find is easier to understand.

public static Node ToTrie(this string[] values)
{
    var root = new Node();
    foreach (var value in values)
    {
        var currentNode = root;
        foreach (var c in value)
        {
            var node = (Node)null;
            if (currentNode.TryGetValue(c.ToString(), out node))
            {
                currentNode = node;
            }
            else
            {
                currentNode = (currentNode[c.ToString()] = new Node());
            }
        }
        currentNode.IsWord = true;
    }
    return root;
}

The Node can actually be simplified too by deriving it from a dictionary. By adding the search method to it you can easily use it on any node. I named it Contains.

Another adjustment you can make is to use string instead of the char so you can use one of the construtor overloads of the dictionary and make it case insensitive. This way you won't need the ToLower.

public class Node : Dictionary<string, Node>
{
    public Node() : base(StringComparer.OrdinalIgnoreCase) {}

    public bool IsWord { get; set; }

    public bool Contains(string value)
    {
        var currentNode = this;
        foreach (var c in value)
        {
            var node = (Node)null;
            if (currentNode.TryGetValue(c.ToString(), out node))
            {
                currentNode = node;
            }
            else
            {
                return false;
            }
        }
        return currentNode.IsWord;
    }
}

Usage:

var result1 = trie.Contains("train"); // True
var result2 = trie.Contains("TraINE"); // False
var result3 = trie.Contains("TRAINEE"); // True
\$\endgroup\$
  • \$\begingroup\$ While I don't necessarily think that all the suggested changes should be implemented in this particular example, they are all very good techniques to keep in mind for future projects. Extending the dictionary is a especially a good idea. I don't think the extension method for the array is necessary in this particular case, as I'm only really making the trie once. The naming of the Contains method in the node is a bit confusing, as it doesn't say anything about the string value being a qualified word, just that it's contained in the trie. Makes it sound like "aine" would be valid. \$\endgroup\$ – tobloef Nov 4 '16 at 23:25
  • \$\begingroup\$ Other than that, these are some very nice suggestions. Thank you. \$\endgroup\$ – tobloef Nov 4 '16 at 23:25

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.