1

我正在尝试解析一个字符串并找到一个常见的空白位置。

这是我的字符串

abc   xyz 123   456
cba 1234a 45623 say
avc  4567 bv    456

可以有任意数量的字符串。我需要一个在 c# 中更可取的通用算法，我可以在其中找到上述字符串中的常见空白位置。

例如，在上面的字符串中，常见的位置是

4, 10 ,16

每个字符串中都有空格。

我一直在尝试的方法包括 Intersect ，并获取所有可能的空间，然后比较找出常见的空间，但我试图找出最佳解决方案。

4

2 回答 2

2 
var stringList = new[] { "abc   xyz 123   456", "cba 1234a 45623 say", "avc  4567 bv    456" };
var shortest = stringList.OrderBy(s => s.Length).First();
var result = new Collection<int>();

for (int i = 0; i < shortest.Length; i++)
{
    if (stringList.All(c => c[i] == ' ')) result.Add(i+1);
}

// Test the results
foreach (var index in result)
{
    Console.WriteLine(index);
}
于 2012-07-05T03:49:19.550 回答
2

在第一个字符串中创建一组空白位置。检查第二个字符串中的这些位置，如果第二个字符串中该位置的字符不是空格，则从集合中删除该位置。对剩余的字符串重复。

另一种可能性是找到每个字符串中空白位置的集合，然后找到这些集合的交集。这将有一个潜在的优势。虽然这通常会完成更多的总工作，但其中的一部分工作（查找单个集合）很容易并行执行。我怀疑这会经常获胜（除非，也许，你有很多弦和很多核心）。虽然它可能不太明显，但您也可以并行找到集合的交点 - 您基本上是做一个二叉树的交点，所以在第一次迭代中您会找到对之间的交点，在第二次您会找到结果对之间的交点从第一次迭代开始，依此类推，直到你只剩下一组。假设至少有许多核心作为字符串，这将时间复杂度从 O(N) 降低到 O(log N)。

于 2012-07-05T03:49:57.047 回答