使用一个或多个循环和“干净"代码在多个级别添加多个唯一子代

问题描述

我是C#初学者，目前我正尝试用各种问题挑战自己.

I’m a C# beginner and at the moment I’m trying to challenge myself with different problems.

目前，我正在尝试构建一个Web应用程序，您可以在其中输入字母和通配符来搜索可能的单词.

At the moment I’m trying to build a web application where you can input letters and wildcards to search after possible words.

对于以前对此的疑问，我决定构建一个Trie，其中包含从40万多个单词生成的字母.稍后，我将在Trie中搜索可能的单词匹配项，具体取决于字母和通配符的输入.

Trough previous questions about this I’ve decided to build a Trie containing letters generated from 400k+ words. Later I’ll search the Trie for possible word matches depending on letter and wildcard input.

我建立了两个类，一个代表Trie中的一个节点，另一个代表整个Trie.

I’ve built two classes, one representing one node in the Trie and one representing the whole Trie.

我目前处于停滞状态，我的问题是我想在多个层次上向Trie添加多个子代，每个子代必须是唯一的.

I’m currently at a standstill, my problem is that I want to add multiple children to the Trie at multiple levels and every child has to be uniqe.

手动执行以下操作:

//Level 1
Root.Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));
//Level 2
Root.Children[0].Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));
//Level 3
Root.Children[0].Children[0].Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));

问题是我想添加带有一个或多个循环的子级，并且这样做似乎有点错误":

Problem is that I want to add children with one or more loops and doing it this way seems a little "wrong":

LetterArray = Word.ToCharArray();
int level = 0;
foreach (char Letter in LetterArray)
{
    //Level 1
    if (level == 0)
        Root.Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));
    //Level 2
    if (level == 1)    
        Root.Children[0].Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));
    //Level 3
    if (level == 2)
        Root.Children[0].Children[0].Children.Add(new TrieNode(Letter, false, new List<TrieNode>()));

    level++;
}

我需要的是一个或多个带有干净"代码的循环，以为您可以帮助我?为了以后可以搜索Trie，我认为这些字母需要顺序排列.这是我与此相关的其他问题:问题1 ，.

What I need is one or more loops with "clean" code, think you can help me?For the Trie to be searchable later the letters needs to come in order i think.Here are my other questions related to this: Question 1, Question 2.

这是我的TrieNode类:

Here’s my TrieNode Class:

public class TrieNode
{
    private char _Letter;
    private bool _IsEndOfWord;
    private List<TrieNode> _Children;

    public char Letter {
        get { return _Letter; }
        set { _Letter = value; }
    }
    public bool IsEndOfWord {
        get { return _IsEndOfWord; }
        set { _IsEndOfWord = value; }
    }
    public List<TrieNode> Children {
        get { return _Children; }
        set { _Children = value; }
    }

    public TrieNode(char letter, bool isEndOfWord, List<TrieNode> children) {
        Letter = letter;
        IsEndOfWord = isEndOfWord;
        Children = children;
    }
}

…这是我的Trie课:

… and here is my Trie Class:

public class Trie
{
    private TrieNode _Root;

    public TrieNode Root
    {
        get { return _Root; }
        set { _Root = value; }
    }

    public Trie(List<string> Words)
    {
        Root = new TrieNode('^', false, new List<TrieNode>());
        char[] LetterArray;

        foreach (String Word in Words)
        {
            LetterArray = Word.ToCharArray();

            foreach (char Letter in LetterArray)
            {
                // Here is where I want to add nodes to my Trie
            }
        }
    }
}

推荐答案

我也可以通过递归来实现，但是我的递归方法将在TrieNode类中:

I'd accomplish this through recursion as well, however my recursive method would be inside the TrieNode class:

public AddWord(string word)
{
    if (String.IsNullOrEmpty(word))
    {
        throw new ArgumentException("word must contain values.", word);
    }

    var letter = word[0];
    var child = Children.FirstOrDefault(x => x.Letter = letter);

    if (child == null)
    {
        //The child doesn't exist.  Create it.
        child = new TrieNode(letter, false, new List<TrieNode>());
    }

    if (word.Length > 1)
    {
        child.AddWord(word.Substring(1);
    }
    else
    {
        child.IsEndOfWord = true;
    }
}

最后，您只需要在Trie构造函数中更改初始循环即可:

Finally you just have to change your initial loop in your Trie constructor:

foreach (String Word in Words)
{
    _Root.AddWord(Word);
}

(注意:我尚未测试此代码，因此可能会有错别字).

(note: I haven't tested this code so there may be typos).

这篇关于使用一个或多个循环和“干净"代码在多个级别添加多个唯一子代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！