Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.
brute force?
determine whether a word is palindrome, we need O(N)
therefore the complexity for brute force is O(N^2*M) = 5000^2 * 300 = 2500000000
no...
if two words can be combined to a palindrome, it means s[0]...s[N] q[0] ... q[M]
s[0] == q[M] s[1] == q[M-1]
it's hard; let me see the std;
first set in c++ is sorted from small to big
the std first use a hash set to record each words' positions
the it's only need to determine whether <= lenght's words exist in the hash set and from d to len-1 is a valid palindrome
for example abb; we only need to find length < 4 all substr (e.g a) in the hashset and ensure the substr after a is a palidornme!
bba, a then we can paste a the first;
So clever. use hashset to do the find operations!