c# - 搜索字符串的数据结构

Question

我正在为以下情况寻找最好的数据结构：在我的情况下，我将有数千个字符串，但是对于这个例子，出于显而易见的原因，我将使用两个。所以假设我有字符串“Water”和“Walter”，我需要的是当输入字母“W”时要找到两个字符串，当输入“Wat”时，“Water”是唯一的结果。我做了一项研究，但是我仍然不太确定哪种数据结构适合这种情况，如果我不确定，我不想实施它，因为这会浪费时间。所以基本上我现在想的是“Trie”或“Suffix Tree”。似乎“Trie”可以解决问题，但正如我所说，我需要确定。此外，实现应该不是问题，所以我只需要知道正确的结构。如果有更好的选择，请随时告诉我。正如您可以猜到的那样，Dictionary/MultiDictionary 等普通结构将无法正常工作，因为这将成为内存杀手。我还计划实施缓存以限制内存消耗。很抱歉没有代码，但我希望我能得到答案。先感谢您。

Answer 1

你应该用户Trie. 尝试是已知最快的排序算法之一（burstsort）的基础，它也用于拼写检查，并用于使用文本完成的应用程序中。您可以在此处查看详细信息。

Answer 2

实际上，如果您想做自动建议，那么最多存储 3-4 个字符就足够了。我的意思是建议当用户键入“a”或“ab”或“abc”并且他键入“abcd”或更多字符的那一刻，您可以使用以“abcd”开头的 map.keys 使用 c# 语言支持 lamda 表达式。

因此，我建议，创建一个类似的地图： Map<char, <Map<char, Map<char, Set<string>>>>> map; 因此，如果用户输入“a”，您将查找 map[a] 并找到所有子项。