java - Efficiently finding the intersection of a variable number of sets of strings

Question

I have a variable number of ArrayList's that I need to find the intersection of. A realistic cap on the number of sets of strings is probably around 35 but could be more. I don't want any code, just ideas on what could be efficient. I have an implementation that I'm about to start coding but want to hear some other ideas.

Currently, just thinking about my solution, it looks like I should have an asymptotic run-time of Θ(n²).

Thanks for any help!

tshred

Edit: To clarify, I really just want to know is there a faster way to do it. Faster than Θ(n²).

question from:https://stackoverflow.com/questions/2851938/efficiently-finding-the-intersection-of-a-variable-number-of-sets-of-strings

Answer 1

Set.retainAll() is how you find the intersection of two sets. If you use HashSet, then converting your ArrayLists to Sets and using retainAll() in a loop over all of them is actually O(n).