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

Question

我有两个元素，x和Y。x是一个很长的字符列表。Y是一个更长的列表，因此它的每个元素都是一个集合。对于 中的每个元素，我想找到包含它的x集合的索引。Y

• 这些集合是不相交的 - 没有元素出现在多个集合中。
• 中的所有元素都x被 中的集合覆盖Y。
• 不存在yinY使得它包含不在 on 上的元素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)]