如何在c＃中创建一个trie [英] How to create a trie in c#

问题描述

有没有人知道在哪里可以找到一个如何在C＃中构建一个特技的例子。我正在尝试一个字典/单词列表，并用它创建一个特技。

解决方案

这是我自己的代码，从我的答案拉回到如何找到一个字来自字符数组：

  public class Trie 
 {
 public struct Letter 
 {
 public const string Chars =ABCDEFGHIJKLMNOPQRSTUVWXYZ; 
 public static implicit operator Letter（char c）
 {
 return new Letter（）{Index = Chars.IndexOf（c）}; 
} 
 public int索引; 
 public char ToChar（）
 {
 return Chars [Index]; 
} 
 public override string ToString（）
 {
 return Chars [Index] .ToString（）; 
} 
} 
 
 public class Node 
 {
 public string Word; 
 public bool IsTerminal {get {return Word！= null; }} 
 public Dictionary< Letter，Node> Edges =新词典< Letter，Node>（）; 
} 
 
 public Node Root = new Node（）; 
 
 public Trie（string [] words）
 {
 for（int w = 0; w< words.Length; w ++）
 {
 var word = words [w]; 
 var node = Root; 
 for（int len = 1; len< = word.Length; len ++）
 {
 var letter = word [len  -  1]; 
 Node next; 
 if（！node.Edges.TryGetValue（letter，out next））
 {
 next = new Node（）; 
 if（len == word.Length）
 {
 next.Word = word; 
} 
 node.Edges.Add（letter，next）; 
} 
 node = next; 
} 
} 
} 
  

Does anyone know where I can find an example of how to construct a trie in C#. I'm trying to take a dictionary/list of words and create a trie with it.

解决方案

This is my own code, pulled from my answer to How to find a word from arrays of characters? :

public class Trie
{
  public struct Letter
  {
    public const string Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    public static implicit operator Letter(char c)
    {
      return new Letter() { Index = Chars.IndexOf(c) };
    }
    public int Index;
    public char ToChar()
    {
      return Chars[Index];
    }
    public override string ToString()
    {
      return Chars[Index].ToString();
    }
  }

  public class Node
  {
    public string Word;
    public bool IsTerminal { get { return Word != null; } }
    public Dictionary<Letter, Node> Edges = new Dictionary<Letter, Node>();
  }

  public Node Root = new Node();

  public Trie(string[] words)
  {
    for (int w = 0; w < words.Length; w++)
    {
      var word = words[w];
      var node = Root;
      for (int len = 1; len <= word.Length; len++)
      {
        var letter = word[len - 1];
        Node next;
        if (!node.Edges.TryGetValue(letter, out next))
        {
          next = new Node();
          if (len == word.Length)
          {
            next.Word = word;
          }
          node.Edges.Add(letter, next);
        }
        node = next;
      }
    }
  }

这篇关于如何在c＃中创建一个trie的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！