1

我是 C# 初学者，目前我正在尝试用不同的问题挑战自己。

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

通过之前关于此的问题，我决定构建一个包含从 400k+ 单词生成的字母的 Trie。稍后我将根据字母和通配符输入在 Trie 中搜索可能的单词匹配。

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

我目前处于停顿状态，我的问题是我想在多个级别向 Trie 添加多个孩子，并且每个孩子都必须是唯一的。

手动执行此操作看起来像这样：

//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>()));

问题是我想添加一个或多个循环的孩子，这样做似乎有点“错误”：

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 稍后可以搜索，我认为这些字母需要按顺序排列。这是我与此相关的其他问题：Question 1，Question 2。

这是我的 TrieNode 类：

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 课程：

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
            }
        }
    }
}
4

2 回答 2

2

你在寻找递归吗？
http://en.wikipedia.org/wiki/Recursion_%28computer_science%29

using System.Linq;

public Trie(List<string> words)
{
    Root = new TrieNode('^', false, new List<TrieNode>());
    // Might have gotten the wrong method, check with intellisense
    char[] letters = words.SelectMany( word => word.ToCharArray());
    RecursiveAdd(letters, Root, 0);
}

private const int desiredDepth = 5;
private void RecursiveAdd(char[] letters, TrieNode branch, currentDepth)
{
    foreach(char letter in letters) {
        TrieNode node = new TrieNode(Letter, false, new List<TrieNode>());
        branch.Children.Add(node);
        if( currentDepth < desiredDepth ) {
            RecursiveAdd(letters, node, currentDepth+1);
        }
    }
}

我希望这会有所帮助，如果我为你做了太多的工作，我很抱歉。我同意，
最好的学习方式就是做事。

于 2011-09-19T17:48:46.060 回答
1

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

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 构造函数中更改初始循环：

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

（注意：我没有测试过这段代码，所以可能有错别字）。

于 2011-09-19T18:29:57.693 回答