比较两个字符串列表并计算匹配项，可能存在性能问题

Question

我想在将字符串列表 A 与另一个字符串列表 B 进行比较时计算匹配项的数量。A 包含集合 Z 中的元素，而 B 是 Z 的子集。A 可以包含重复项，但 B 不能。我希望单独计算重复项，因此与 B 中的相同元素进行 2x 匹配应该产生 2 个计数。列表 A 的字符串包含一个前缀，我决定将其删除，但我也可以不修改原始字符串元素

示例：

List<string> A = {"a","b","c","a"}
List<string> B = {"a", "c"}

匹配为 3（两次与 a 匹配，一次与 c 匹配）

我有一个应该有效的解决方案，在极少数情况下它确实有效，但我怀疑由于执行期间的时间限制，它有 90% 的时间会失败。

var _A = A.Select(str => str.ToLower()).ToList(); //B can be modified for this step to be not necessary but increases the length of each string element
_A = _A.Select(str => str.Replace(" ", "")).ToList(); //B can be modified for this step to be not necessary but increases the length of each string element
_A = _A.Select(x => x.Substring("drops".Length)).ToList(); //B can be modified for this step to be not necessary but increases the length of each string element

sum = _A.Where(x => B.Any(y => y.Equals(x))).Count();

如果我没记错的话，这是O(A*B)。

我还能做些什么来降低时间复杂度吗？

Answer 1

您使用 HashSet<string>。在 Add() and Contains().

中都是 O(1)

var a = new[] { "a", "b", "c", "a" };
var b = new[] { "a", "c" };

var hs = new HashSet<string>(b);
var cnt = a.Count(x => hs.Contains(x));

复杂度为 O(b+a)，Add() 为 O(b)，Contains() 为 O(A)。

比较两个字符串列表并计算匹配项，可能存在性能问题

Comparing two lists of Strings and counting the matches, possible performance problem

c#

linq

string

list

matching