C#如何比较两个字符串中的匹配单词

Question

C#如何比较两个字符串中的匹配单词

c#string

7

我有两个包含字母和数字的字符串，由空格分隔。例如："elza7ma wa2fa fel matab" 和 "2ana ba7eb el za7ma 2awy 2awy"

最快的方法是什么，可以比较这两个字符串并找出它们是否有相同的单词？

我尝试使用 string.split 将其中一个字符串拆分，并在整个单词数组上使用 string.compare 进行比较。但这非常慢，因为我将比较很多字符串。

- Marwan

似乎indexOf比正则表达式更快，但不知道它是否比string.compare更快 : )。你可以尝试一下。 - Danil

1

你真的需要“最快”吗？你可能需要在这个问题上工作几年。我猜你只是想要“足够快”，如果是这样，那么你没有提供足够的信息来解决问题。你的硬件是什么？你的时间预算是多少？通常的问题规模是多少？ - Eric Lippert

3

“很多字符串”是什么意思？你下面的评论表明，“很多”指的是几百个。我认为几百个字符串是一个极小的数量。这个描述准确吗？我认为“很多”的数量应该是数百万或数十亿个字符串，就像Bing索引了许多字符串一样。如果没有对问题的规模有一个好的了解，很难给你一个好的答案。 - Eric Lippert

5个回答

5

我认为最简单的方法是将字符串拆分为单词，并使用类似于HashSet<string>的集合结构来检查重复项。例如：

public bool HasMatchingWord(string left, string right) { 
  var hashSet = new HashSet<string>(
    left.Split(" ", StringSplitOptions.RemoveEmptyEntries)); 
  return right
    .Split(" ", StringSplitOptions.RemoveEmptyEntries)
    .Any(x => hashSet.Contains(x));
}

- JaredPar

1

可能还需要添加一个相等性检查来处理碰撞（如果有的话）。 - Jeff Mercado

1

你可以按单词拆分这两个字符串，并构建两个哈希表/字典。然后遍历这两个哈希表/字典，将键添加到第三个字典中并递增一个整数（Dictionary<string, int>）。如果第三个字典中的任何键计数超过一，则该单词在原始字符串中都存在。

我认为解决这个问题的任何算法都会比较“慢”-特别是对于大型输入字符串/许多单词。

- Michael Banzon

将所有单词添加到同一个HashSet中，并检查Add()方法的返回值会更简单。 - Sjoerd

我重新阅读了原始问题 - 是的，这会简单得多。他只是在问是否有任何单词在两个字符串中都出现 - 不是哪些单词，也不是出现次数。 - Michael Banzon

0

我可能会承受最初的性能损失，将字符串拆分并按字母顺序和单词长度排序。如果你只需要找出一个单词是否匹配，那么一旦找到一个就可以停止。一旦你将拆分的字符串数组按字母顺序和长度排序，这就限制了你需要进行比较的数量。

- Matt

0

最简单的方法是将所有单词与任何其他单词进行比较。这是一种简单的解决方案，但速度较慢。
另一种方法是对两个列表进行排序，然后比较前两个条目。类似于归并排序，但其目标是找到相等的单词。
另一种方法是将单词列表编译成树，并将单词与该树匹配。可以使用正则表达式来实现，也可以自己实现。在您的示例中，第一个字母应为2、b、e或z。这样，每个单词只被检查一次，且检查的字符数最少。

- Sjoerd

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Russ Cam · Accepted Answer

一个 LINQ 解决方案

"elza7ma wa2fa fel matab".Split()
                         .Intersect("2ana ba7eb el za7ma 2awy 2awy".Split())
                         .Any();

// as a string extension method
public static class StringExtensions
{
    public static bool OneWordMatches(this string theString, string otherString)
    {
        return theString.Split().Intersect(otherString.Split()).Any();
    }
}

// returns true
"elza7ma wa2fa fel matab 2ana".OneWordMatches("2ana ba7eb el za7ma 2awy 2awy");