【求算法】多条字符串求并集

Question

任意n条字符串，每条字符串包含m个字符，现在要求把字符串包含相同的合并。得出他们最大的并集。
例如：
a ，b，c
b，e，d
f，g,h合并之后
a,b,c,d,e
f,g,h请问算法怎么写，难道用list<ArrayList>两条两条的遍历合并？还有什么比较快的方法？

Answer 1

用Dictionary<string, bool>，或.Net1.1下的HashTable。

Answer 2

如果你要找字符的并集，并能确定所有的字符都是ASCII字符，那么准备一个数组
bool[] masks = new bool[128];然后对取出的每个字符c进行打勾：
masks[(int)c] = true;最后masks中标记为true即为你要的并集
for(int i=0; i<masks.Length; i++)
{
   if( mask[i] ) Console.WriteLine( (char)i );
}

Answer 3

这个不错！另：可以把所有字符放到一个list里面
可以list.sort()做下排序。然后消除掉重复值。

Answer 4

先收藏此题用C#是肯定要用StringBuilder类的，否则字符串拼接效率肯定不高

Answer 5

那可未必,仅当你在一个循环里进行超过 600 次的字符串连接时，使用 StringBuilder 来获得更好的速度。这里需要提醒的是，你所处理的字符串的长度也会影响最终的速度，同样会影响垃圾收集器的效果，所以你应该根据你实际的代码具体问题具体分析

Answer 6

少量的话用正则很方便。string[] array = new string[] { 
    "a,b,c",
    "b,e,d",
    "f,g,h"
};
string all = String.Join(",", array);
Console.WriteLine(Regex.Replace(all, @"(?:^|,)([^,]+)(?=,.*?\1)", "").TrimStart(','));

Answer 7

string[] array = new string[] { 
    "a,c,b",
    "b,e,d",
    "f,g,h",
    "xx,x,xxx"
};
string all = String.Join(",", array);
Console.WriteLine(Regex.Replace(all, @"(?:^|,)([^,]+)(?=(,.+)*,\1(?:,|$))", "").TrimStart(','));