algorithm - Given an array of arrays which contain characters, find all the arrays with at least one common character and return them as pairs -

brute force method 1. compare each array array 2. if there 1 common character; print pair time: o(n3)

how optimize this?

lets characters ascii. number of possible characters 256

example:

your_array = [['abc'], ['dxf'], ['xyz'], ['axd']] 

lets, indices[256] array of array indices[i] contain index of arrays have character ascii code i.

indices[97] = [0, 3] // ascii code 97 indices[98] = [0] // indices[99] = [0] indices[100] = [1, 3] indices[120] = [1, 2, 3] indices[102] = [1] indices[121] = [2] 

now, generate pairs each indices size(indices) > 1

for indices[97]  pairs: <['abc'], ['axd']>  ......  ......  ......  indices[120]  pairs: <['dxf'], ['xyz']> <['dxf'], ['axd']> <['xyz'], ['axd']> 

the space complexity o(n) n number of array of characters.

time complexity build indices array o(n) , printing pairs o(n^2) in worst case. however, printing pairs(yielding output) compulsory problem, complexity beyond consideration.