Problem: Given n strings, check if exist 2 of strings which can group a palindrome.
For example, for strings ‘aaa’, ‘aac’, ‘ab’, ‘acblb’, ‘ac’, ‘ddcaa’.
‘aac’ and ‘ddcaa’ can group into palindrome; ‘acblb’ and ‘ac’ can group into palindrome.
We can solve this problem using trie and rolling hash queue. For example, below is when first 4 words in trie:
Next, check word ‘ca’ in reverse sequence. Search it in trie. And it ends in string first. Then, we check any descendant of last node contains a palindrome. And we found b-l-b is a palindrome. So, we conclude word ‘acblb’ and ‘ca’ can group to a palindrome string.
Next, check word ‘ddcaa’ in reverse sequence. Search it in trie. And it ends in trie first. Then, we check if rest string in ‘ddcaa’ is palindrome, which is ‘dd’. And we found ‘dd’ is palindrome. So, we conclude word ‘aac’ and ‘ddcaa’ can group to a palindrome string.
I’m a bit lazy to write the trie code. It would a kinda long code. So, I summarized the basic idea of the solution. But this requires how to find a palindrome in tree, which is talked in my last post http://allenlipeng47.com/PersonalPage/index/view/165/nkey