实现一个高效的算法来找到两个字符串的交集

Question

实现一个算法,该算法将两个字符串作为输入,并返回两者的交集,每个字母最多表示一次.

Algo :(考虑使用的语言将是c#)

1. 将两个字符串转换为char数组
2. 获取较小的数组并为其生成哈希表,其中键为字符,值为0
3. 现在循环遍历另一个数组并在散列表中增加计数(如果该字符存在于其中).
4. 现在取出值为> 0的哈希表的所有char.
5. 这些是交叉值.

这是一个O(n)解决方案但是使用了额外的空间,2个char数组和一个哈希表

你能想到比这更好的解决方案吗？

Answer 1

这个怎么样 ...

var s1 = "aabbccccddd";
var s2 = "aabc";

var ans = s1.Intersect(s2);