字符串解析并查找公共空格位置

Question

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

这是我的字符串

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

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

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

4, 10 ,16 

每个字符串中都有空格。

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

Answer 1

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);
}

Answer 2

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

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