高效的单词列表搜索

Question

我正在制作一个程序，每次注册一封信时都需要在整个单词列表中搜索有效单词（数十千个单词）。问题是，字母不一定按顺序排列。您可以按顺序注册“O”、“G”、“R”和“F”来拼写“frog”。另外，仅仅知道是否有有效的单词是不够的。我必须知道它是哪个词。

所以问题是：每次注册信件时都使用 IndexOf() 方法是我唯一的选择吗？或者有更有效的方法吗？ 顺便说一句，它将是 C#。

提前谢谢您

我尝试了 IndexOf 方法，但遍历数千个单词似乎效率不高。

Answer 1

如果您正在 C# 中搜索大量单词，并希望根据注册字母有效查找有效单词，您可以考虑使用 trie（前缀树）等数据结构。尝试对于搜索字符串集特别有效，使其非常适合单词搜索场景。

using System;
using System.Collections.Generic;

public class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; set; }
    public bool IsEndOfWord { get; set; }
    public List<string> Words { get; set; }

    public TrieNode()
    {
        Children = new Dictionary<char, TrieNode>();
        IsEndOfWord = false;
        Words = new List<string>();
    }
}

public class WordTrie
{
    private TrieNode root;

    public WordTrie()
    {
        root = new TrieNode();
    }

    public void InsertWord(string word)
    {
        TrieNode node = root;

        foreach (char c in word)
        {
            if (!node.Children.ContainsKey(c))
            {
                node.Children[c] = new TrieNode();
            }

            node = node.Children[c];
        }

        node.IsEndOfWord = true;
        node.Words.Add(word);
    }

    public List<string> FindWordsWithPrefix(string prefix)
    {
        TrieNode node = root;

        foreach (char c in prefix)
        {
            if (node.Children.ContainsKey(c))
            {
                node = node.Children[c];
            }
            else
            {
                // Prefix not found
                return new List<string>();
            }
        }

        return node.Words;
    }
}

class Program
{
    static void Main()
    {
        WordTrie trie = new WordTrie();
        string[] words = { "frog", "apple", "orange", "table", "bat" };

        foreach (string word in words)
        {
            trie.InsertWord(word);
        }

        // Example: Searching for words with the prefix "fro"
        List<string> foundWords = trie.FindWordsWithPrefix("fro");

        foreach (string word in foundWords)
        {
            Console.WriteLine(word);
        }
    }
}