有效地查找列表<；字符串>；以另一个字符串开头

本文关键字：字符串 另一个 开头 gt 查找 lt 有效地 列表 | 更新日期: 2023-09-27 18:30:01

我有一个字符串列表。我想找到所有以另一个字符串开始或结束的字符串。最简单的例子是：；

List<string> allWords = new List<string>();
for(int index = 0; index < 1000000; index++)
    allWords.Add(index.ToString());
List<string> result = allWords.FindAll(x => x.StartsWith("10") || x.EndsWith("10"));

该算法从头到尾扫描列表。我需要非常快地执行此操作，而O（n）太慢了。

什么数据结构（如果有的话）对我来说可以比O（n）更快地解决这个算法？

有效地查找列表<；字符串>；以另一个字符串开头

如果您有一个未排序的List<string>，没有办法在小于O(n)的时间内完成。但是，您可以使用不同的数据结构。trie（也称为前缀树）特别适合您的需要，因为它具有O(m)搜索复杂性（其中m是搜索前缀的长度）

我在这里有一个C#实现：Trie.cs（实际上，它是一个基于Trie的字典，它将一个值与每个键相关联，但对于您的用例，您可以忽略该值；或者，如果您愿意，可以根据您的需求调整实现）。

  1. 要查找以给定子字符串开头的字符串，请对列表进行排序，进行二进制搜索以查找最匹配的字符串，然后扫描相邻的字符串以查找与开头匹配的其他字符串。这是log（n）

  2. 要查找以给定子字符串结尾的字符串，请创建一个反向字符串列表，并对该列表进行排序。然后，要找到以给定模式结束的字符串，请反转该模式并查找以反转模式开始的反转字符串，如步骤1所示。

相关文章：