LeetCode: Replace Words Trie C#

Question

I am trying to solve this leet code problem
https://leetcode.com/problems/replace-words/

Please comment about performance.

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

The input will only have lower-case letters. 1 <= dict words number <= 1000 1 <= sentence words number <= 1000 1 <= root length <= 100 1 <= sentence words length <= 1000

using System;
using System.Collections.Generic;
using System.Collections.Generic;
using System.Security.Policy;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TrieQuestions
{
 public class TrieNode
    {
        public Dictionary<char, TrieNode> Edges { get; set; }
        public bool IsTerminal { get; set; }
        public TrieNode()
        {
            Edges = new Dictionary<char, TrieNode>();
        }
    }

    [TestClass]
    public class TrieReplaceWords
    {
        [TestMethod]
        public void ReplaceWordsTest()
        {
            List<string> dict = new List<string> { "cat", "bat", "rat" };
            const string sentence = "the cattle was rattled by the battery";
            const string output = "the cat was rat by the bat";
            Assert.AreEqual(output, ReplaceWords(dict, sentence));
        }

        [TestMethod]
        public void LeetCodeLongTest()
        {
            List<string> dict = new List<string> {
                "e", "k", "c", "harqp", "h", "gsafc", "vn", "lqp", "soy", "mr", "x", "iitgm", "sb", "oo", "spj", "gwmly", "iu", "z", "f", "ha", "vds", "v", "vpx", "fir", "t", "xo", "apifm", "tlznm", "kkv", "nxyud", "j", "qp", "omn", "zoxp", "mutu", "i", "nxth", "dwuer", "sadl", "pv", "w", "mding", "mubem", "xsmwc", "vl", "farov", "twfmq", "ljhmr", "q", "bbzs", "kd", "kwc", "a", "buq", "sm", "yi", "nypa", "xwz", "si", "amqx", "iy", "eb", "qvgt", "twy", "rf", "dc", "utt", "mxjfu", "hm", "trz", "lzh", "lref", "qbx", "fmemr", "gil", "go", "qggh", "uud", "trnhf", "gels", "dfdq", "qzkx", "qxw"};
            const string sentence = "ikkbp miszkays wqjferqoxjwvbieyk gvcfldkiavww vhokchxz dvypwyb bxahfzcfanteibiltins ueebf lqhflvwxksi dco kddxmckhvqifbuzkhstp wc ytzzlm gximjuhzfdjuamhsu gdkbmhpnvy ifvifheoxqlbosfww mengfdydekwttkhbzenk wjhmmyltmeufqvcpcxg hthcuovils ldipovluo aiprogn nusquzpmnogtjkklfhta klxvvlvyh nxzgnrveghc mpppfhzjkbucv cqcft uwmahhqradjtf iaaasabqqzmbcig zcpvpyypsmodtoiif qjuiqtfhzcpnmtk yzfragcextvx ivnvgkaqs iplazv jurtsyh gzixfeugj rnukjgtjpim hscyhgoru aledyrmzwhsz xbahcwfwm hzd ygelddphxnbh rvjxtlqfnlmwdoezh zawfkko iwhkcddxgpqtdrjrcv bbfj mhs nenrqfkbf spfpazr wrkjiwyf cw dtd cqibzmuuhukwylrnld dtaxhddidfwqs bgnnoxgyynol hg dijhrrpnwjlju muzzrrsypzgwvblf zbugltrnyzbg hktdviastoireyiqf qvufxgcixvhrjqtna ipfzhuvgo daee r nlipyfszvxlwqw yoq dewpgtcrzausqwhh qzsaobsghgm ichlpsjlsrwzhbyfhm ksenb bqprarpgnyemzwifqzz oai pnqottd nygesjtlpala qmxixtooxtbrzyorn gyvukjpc s mxhlkdaycskj uvwmerplaibeknltuvd ocnn frotscysdyclrc ckcttaceuuxzcghw pxbd oklwhcppuziixpvihihp";
            const string output = "i miszkays w gvcfldkiavww v dvypwyb bxahfzcfanteibiltins ueebf lqhflvwxksi dc k w ytzzlm gximjuhzfdjuamhsu gdkbmhpnvy i mengfdydekwttkhbzenk w h ldipovluo a nusquzpmnogtjkklfhta k nxzgnrveghc mpppfhzjkbucv c uwmahhqradjtf i z q yzfragcextvx i i j gzixfeugj rnukjgtjpim h a x h ygelddphxnbh rvjxtlqfnlmwdoezh z i bbfj mhs nenrqfkbf spfpazr w c dtd c dtaxhddidfwqs bgnnoxgyynol h dijhrrpnwjlju muzzrrsypzgwvblf z h q i daee r nlipyfszvxlwqw yoq dewpgtcrzausqwhh q i k bqprarpgnyemzwifqzz oai pnqottd nygesjtlpala q gyvukjpc s mxhlkdaycskj uvwmerplaibeknltuvd ocnn f c pxbd oklwhcppuziixpvihihp";
            Assert.AreEqual(output, ReplaceWords(dict, sentence));
        }
        [TestMethod]
        public void LeetCodeTest()
        {
            List<string> dict = new List<string> {"a", "aa", "aaa", "aaaa"
            };
            const string sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa";
            const string output = "a a a a a a a a bbb baba a";
            Assert.AreEqual(output, ReplaceWords(dict, sentence));
        }

        public string ReplaceWords(IList<string> dict, string sentence)
        {
            TrieNode root = new TrieNode();
            foreach (var word in dict)
            {
                var current = root;
                foreach (var letter in word)
                {
                    if (!current.Edges.TryGetValue(letter, out var output))
                    {
                        output = current.Edges[letter] = new TrieNode();
                    }
                    current = output;
                }

                current.IsTerminal = true;
            }

            string[] words = sentence.Split(' ');
            StringBuilder str = new StringBuilder();

            foreach (var word in words)
            {
                var current = root;
                StringBuilder tempWord = new StringBuilder();
                for (var index = 0; index < word.Length; index++)
                {
                    var letter = word[index];
                    //if there is no word starting with those letters
                    if (!current.Edges.TryGetValue(letter, out var output))
                    {
                        if (current.IsTerminal)
                        {
                            str.Append(tempWord + " ");
                            break;
                        }

                        str.Append(word + " ");
                        break;
                    }

                    tempWord.Append(letter);
                    //output is terminal for the case we have "a" as a word
                    if (current.IsTerminal || output.IsTerminal )
                    {
                        str.Append(tempWord + " ");
                        break;
                    }
                    if (index == word.Length-1)
                    {
                        str.Append(word + " ");
                    }

                    current = output;
                }
            }

            str.Length--;
            return str.ToString();
        }
    }
}

Answer 1

Break it down into smaller building blocks

The ReplaceWords method does too many things: it implements the behavior of a trie, the logic of finding root words, and splitting the input and forming the output.

It would be better if it looked more like this:

public string ReplaceWords(IList<string> dict, string sentence)
{
    Trie trie = new Trie();

    // for each word in dict, trie.add(word)

    // for each word in sentence, map to trie.wordRoot(word)

    // return joined by space the values returned by trie.wordRoot(word) calls
}

The flow of logic would be very easy to read, understand, debuggable and testable piece by piece.

Custom implementation of trie

To support the logic outlined above, the trie.wordRoot method could be implemented as:

• follow the edges per letter in the word, much like during trie.add
• if no successor is found, that means the word of the sentence is not in the trie, it has no root, so return the word itself
• if a leaf node is found, that means a root is found, return it

I think the result will be simpler and easier to understand than the posted code.

Using a StringBuilder

Instead of str.Append(tempWord + " "), str.Append(tempWord).Append(' ') is probably better.

Performance

You specifically asked to comment about performance, so I try as best as I can. Using a trie as you did seems appropriate for the task, as it is known to be efficient for solving string-related computations like this, as long as its storage requirement is not an issue. And I don't see mistakes in the trie implementation degrade its performance significantly.

The overall time and space complexity of the solution is dominated by that of the trie.