I have two lists of strings, and wish to find all pairs of strings between them that contain no common characters. e.g.
list1 = ['abc', 'cde']
list2 = ['aij', 'xyz', 'abc']
desired output = [('abc', 'xyz'), ('cde', 'aij'), ('cde', 'xyz')]
I need this to be as efficient as possible because I am processing lists with millions of strings. At the moment, my code follows this general pattern:
output = []
for str1 in list1:
for str2 in list2:
if len(set(str1) & set(str2)) == 0:
output.append((str1, str2))
This is O(n^2) and is taking many hours to run, does anyone have some suggestions for how to speed this up? Perhaps there is a way to take advantage of characters in each string being sorted?
Thank you very much in advance!