我是一个c#初学者,目前我正试图用不同的问题挑战自己。
目前我正试图建立一个web应用程序,您可以输入字母和通配符搜索可能的单词。
通过之前关于这个的问题,我决定构建一个包含从400k+单词生成的字母的Trie。稍后,我将根据字母和通配符输入在tree中搜索可能的单词匹配。
我已经构建了两个类,一个代表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++;
}
我需要的是一个或多个循环与"干净"的代码,认为你可以帮助我吗?为了以后可以搜索到,我认为这些字母需要按顺序排列。以下是我与此相关的其他问题:问题1,问题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
}
}
}
}
你在寻找递归吗?
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);
}
}
}
我希望这对你有帮助,如果我为你做了太多的工作,我很抱歉。学习的最好方法是做,我同意。
我也会通过递归实现这一点,但是我的递归方法将在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);
}
(注意:我没有测试过这段代码,所以可能有拼写错误)。