从列表中获取包含字符的集合的索引，对于每个字符，时间复杂度小于 O(n**2)

Question

我有两个元素，

x

和

Y

。

x

是一个很长的字符列表。

Y

是一个更长的列表，因此它的每个元素都是一个集合。对于

x

中的每个元素，我想在

Y

中找到包含它的集合的索引。

• 这些集合是不相交的 - 没有元素出现在多个集合中。

• x

  中的所有元素都被

  Y

  中的集合覆盖。

• y

  中不存在

  Y

  ，因此它包含不在

  x

  上的元素。

Y = [{"a", "b"}, {"c", "d"}, {"e", "f"}]
x = ["a", "b", "c", "d", "e", "f", "a", "f"]

# Desired results:
[('a', 0), 
 ('b', 0), 
 ('c', 1), 
 ('d', 1),
 ('e', 2), 
 ('f', 2),
 ('a', 0),
 ('f', 2)]

坦白说，只要计算高效，我对任何形状的结果都可以。

Answer 1

可以先创建索引，以加快搜索速度：

Y = [{"a", "b"}, {"c", "d"}, {"e", "f"}]
x = ["a", "b", "c", "d", "e", "f", "a", "f"]

index = {v: i for i, s in enumerate(Y) for v in s}
out = [(v, index[v]) for v in x]
print(out)

打印：

[("a", 0), ("b", 0), ("c", 1), ("d", 1), ("e", 2), ("f", 2), ("a", 0), ("f", 2)]