C#中无序字母匹配单词列表的高效搜索方案咨询

核心思路：预处理+哈希表快速查找 #

问题本质是找字母异位词，最高效的方式是提前对单词列表做预处理，把每个单词转换成「排序后的字母串」作为键，原单词作为值存入字典。查询时只需对输入字母排序，直接查字典就能得到所有匹配单词。

具体实现步骤 #

1. 预处理单词列表 #

遍历所有单词，对每个单词的字母排序生成键，将单词添加到对应键的列表中：

// 假设你的单词列表是List<string> wordList
Dictionary<string, List<string>> anagramDict = new Dictionary<string, List<string>>();

foreach (string word in wordList)
{
    // 转为小写统一匹配（按需决定是否区分大小写）
    char[] chars = word.ToLower().ToCharArray();
    Array.Sort(chars);
    string key = new string(chars);
    
    if (!anagramDict.ContainsKey(key))
    {
        anagramDict[key] = new List<string>();
    }
    anagramDict[key].Add(word);
}

2. 处理用户输入并查询 #

用户输入字母后，同样排序生成键，直接从字典中获取匹配结果：

// 假设用户输入的字母是List<char> inputChars（比如从输入框收集的字符）
char[] inputArr = inputChars.Select(c => char.ToLower(c)).ToArray();
Array.Sort(inputArr);
string inputKey = new string(inputArr);

if (anagramDict.TryGetValue(inputKey, out List<string> matches))
{
    // matches就是所有匹配的单词，比如输入O、G、R、F时会返回["frog"]（若有其他异位词也会包含）
    foreach (string match in matches)
    {
        Console.WriteLine(match);
    }
}
else
{
    Console.WriteLine("没有找到匹配的单词");
}

效率对比 #

• 原IndexOf()方案：每次查询需遍历所有单词，对每个单词还要逐个校验字母存在性（还要处理重复字母计数），时间复杂度为O(n*m)（n是单词数，m是单词平均长度），数万条数据下每次查询都很慢。
• 预处理方案：预处理仅执行一次，时间复杂度为O(k*m log m)（k是单词数，排序单单词字母为O(m log m)）；后续每次查询仅需对输入字母排序（O(t log t)，t是输入字母数）+ 字典查询（O(1)），多次查询场景下效率提升极其明显。

额外优化点 #

• 若需区分大小写，去掉代码中的ToLower()即可。
• 排序方式天然支持重复字母匹配：比如输入两个O，排序后的键会包含两个O，只有单词中有两个O的才会被匹配，无需额外逻辑。
• 若单词列表存在重复项，可用HashSet<string>替代List<string>存储值，节省内存。

内容的提问来源于stack exchange，提问作者Ahmet Akif Şahin