CareerCup

Looks like you can actually make it O(NK). Basically you create a trie and any time you process a word you check if it is in the trie. If it is, you return true, if not you add reverse of the word to trie and continue to the next one. If you added the last word, it means the answer is no.

Maintain 2 tries, one for all words and one for reverse of all words.

For each word w:

1. Search for w in reverse-trie.
Possible results:
- Exact match is found (palindrome found)
- If a leaf or the end of some word in trie is hit before reaching the end of w, the remainder of w must be a palindrome in order for there to be a palindrome with the path traversed so far in the trie

2. Search for reverse of w, w' in non-reverse-trie.
Possible results:
- Exact match is found (palindrome found)
- If we reach the end of w' before hitting the end of a word in the trie, some remainder of the trie rooted at this ending node must be a palindrome in order for there to be a palindrome
- If a leaf is hit before reaching the end of w', then there is no palindrome yet

3. Add w into the non-reverse trie and add w' into the reverse trie

Time complexity: O(k) to reverse each word, traverse tries, and insert into tries * O(n) words = O(kn)

If we know all words are of the same length, then that greatly simplifies the solution and we can simply convert a list of words into a hash set and search for the reverse of each word in the set, which is also O(kn).

what is k here?

This is my solution in python in O(n^2):

def isPalindrome(string):
	str_length = len(string)
	start = 0 ;
	end = str_length-1

	while(start < end ):
		if( string[start] is not string[end]):
			return False
		
		start+=1
		end-=1
	return True


def testpalindrome(array):
	length = len(array)
	i=0
	pal_dict = dict()
	palindrome_indexes = []
	comparisons = 0;
	while ( i < length):
		j=0
		while( j < length):
			if( i != j):
				key = str(j)+str(i)
				if( key in pal_dict ):
					palindrome_indexes.append(key)
					pal_dict[key]=1
					palindrome_indexes.append(array[i] +"-" + array[j])
				else:
					full_string = array[i] + array[j]
					if( isPalindrome(full_string)):
						palindrome_indexes.append(array[i] +"-" + array[j])
						if( len(array[i]) == len(array[j])):
							pal_dict[str(i)+str(j)]=1
					comparisons+=1
			j+=1
		i+=1

	print "Comparisons : "+ str(comparisons) + "( " + str(length)+ " ) "+ " palindrome indexes: " + str(palindrome_indexes)


testpalindrome(["bat","tabloid","cat","junk"]);   
testpalindrome(["bat","tabloid","cat","ototac","junk"]);   
testpalindrome(["bat","tabloid","cat","tacoto","junk"]);   
testpalindrome(["tacoto","bat","tabloid","cat","junk"]);

I was wondering if we can solve using DP, the intent is to make use of the comparisons already done for palindrome matched pairs. For e.g. if the list is (abc, cat, rat, tac, pat) since cat & tac are palindromes, reuse the comparison results done for cat when iterating for tac.
And also we do not have to compare previous words in the list as we iterate.
If you look at the 2d table, we have to compute only n^2/2 entries as the lower half of the table is self filled and in the remaining entries, palindrome pairs don't have to be recomputed.

{
public class Palindrome {

public static String reverse(String A) {
String reverse = "";
for (int i = A.length()-1; i >= 0; i--) {
reverse = reverse + A.charAt(i);
}
return reverse;
}

public static void main(String[] args) {
String[] s = { "bat", "tab", "cat", "tac", "deepak", "garg" };
Map<String, String> wordReverseMap = new HashMap<String, String>();

for (int i = 0; i < s.length; i++) {
if (wordReverseMap.containsKey(s[i])) {
System.out.println(s[i] + " " + wordReverseMap.get(s[i]));
} else {
wordReverseMap.put(Palindrome.reverse(s[i]), s[i]);
}
}
}
}
}

I think we can solve this problem like this
For simplicity Lets assume that given words are only alphabetical words, we can expand it further no other characters. Also assume that all alphabets are lower case. We can amend algo to accommodate both case.

Two words can be palindrome combined if start char of one is same as end char of another word. Here Idea is create 2 Maps, one for the start char of each word and another for end char of each word.If there are more then one words with same start or end char then they should be stored in the linked list for same key.

Pseudo code:

1. Take two map. Key of the map is char and Value is a list with each node containing a word

2. Iterate through the given array of words

3. For each word, create entry in the first Map for the first char of the word
e.g. for word "pramod" add key value p -> pramod

4. Also create entry in second map for the last char of the word
e.g. for word "pramod" add key value d -> pramod

These steps will complete in O(n) time

5. Now lets iterate through all Keys of the First Map

6. For each key found, get its corresponding value list e.g. key "p" with value "pramod", "praveen" "prime"

7. Iterate over each word in the list for key "P"
Check last char of the value e.g. "d" here for "pramod"

8. Look for the entry in another map with key "d"
8.1 If entry not found there is no possibility of palindrome for this word, just skip it
8.2 If entry found then look for the palindrome property of the word in second dictionary.
8.2.1 If both are the match then save it into the result

O(n) to iterate through all keys
For each key we are comparing only with words which ends by same char so discarding everything else. This is reducing the comparison from O(n2) to O(n) best case. However in worst case it can turn out to O(n2). Eg if all words given starts with 'p' and ends with 'd'

I am thinking if we can further improve this algo to make it work O(n) for worst case
I am ignoring O(k) which is implicit here when words are compared for palindrome

Please point out any mistake in algo or computation of complexity

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms_Learning
{
    class  TrieNode
    {
        private Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
        private string word;
        public void AddString(string s, string word)
        {
            if (s == "$")
            {
                this.word = word;
                return;
            }
            char character = s[0];
            TrieNode child;
            if (Children.ContainsKey(character))
                child = Children[character];
            else
            {
                child = new TrieNode();
                Children[character] = child;
            }
            if (s.Length == 1)
            {
                child.AddString("$", word);
            }
            else
            {
                string newString = s.Remove(0, 1);
                child.AddString(newString, word);
            }
        }
        public List<string> GetChildWords()
        {
            List<string> result = new List<string>();
            if (word != "")
                result.Add(word);
            else
            {
                foreach (TrieNode child in Children.Values)
                {
                    result.AddRange(child.GetChildWords());
                }
            }
            return result;


        }
        public List<string> GetWordsStartingWith(string prefix)
        {
            char firstCharacter = prefix[0];
            if (prefix.Length==1)
            {

                if (Children.ContainsKey(firstCharacter))
                {
                    TrieNode child = Children[firstCharacter];
                    return child.GetChildWords();
                }
                else
                    return new List<string>();
            }
            else
            {
                if (Children.ContainsKey(firstCharacter))
                {
                    TrieNode child = Children[firstCharacter];
                    string newString = prefix.Remove(0, 1);
                    return child.GetWordsStartingWith(newString);
                }
                else
                    return new List<string>();
            }
        }

    }
   
    class Program
    {
       

        
        static void Main(string[] args)
        {
            List<string> input = new List<string>();
            input.Add("bat");
            input.Add("tab");
            input.Add("tba");
            input.Add("cat");

            FindPalindrome(input);
            
        }

        private static void FindPalindrome(List<string> input)
        {
            TrieNode root = new TrieNode();
            foreach (string s in input)
            {
                root.AddString(s, s);
            }
            foreach (string s in input)
            {
                string reverse = new string(s.Reverse().ToArray());
                List<string> wordsStartingWithReverse = root.GetWordsStartingWith(reverse);
                foreach (string word in wordsStartingWithReverse)
                {
                    if (CanFormPalindrom(word, s))
                    {
                        Console.WriteLine(word + "," + s);
                    }
                }


            }
        }

        static bool CanFormPalindrom(string a,string b)
        {
            string c = a + b;
            for(int i = 0; i<c.Length/2;i++)
            {
                int j = c.Length - 1 - i;
                if (c[i] != c[j])
                    return false;
            }
            return true;
        }
     
     
       
    }
   

}

1. for each word create dictionary entries for possiblePalindrome=>[word]
We do this by:
a) adding an entry for the word reversed if it is not a palindrome.
b) taking any palindrome suffixes of the word and reversing the prefix.
Don't include the first char in this check because there has to be some prefix chars remaining after we find the suffix palindrome so we can know what chars can be added to the suffix palindrome to make it symmetrical.
i.e. For the word 'cata' the palindrome suffixes are 'ata', 'a'.
The dictionary entries for would be: 'c'=>['cata'], 'tac'=>['cata'], 'atac'=>['cata'].
The entry is an array because multiple words might have the same possible palindrome.

2. Now for each word in the list you can look up the words that are palindrome pairs.

findPalindromePairs(['cata', 'c', 'atac', 'tac', 'cat', 'a']);
returns 
   atac, cata
   cata, c
   cata, atac
   cata, tac
   cat, tac
   tac, cat

function findPalindromePairs(list, hash) {

  // for each word, add entries for each possible palindrome pair
  // build dictionary of possiblePalindromePair=>[word] // several words might have same palindrome pairs
  
  list.forEach(function (word) {
    findPossiblePalindromePairs(word, hash);
  });

  // look up each word in the list from the dictionary
  var pairs = [];
  list.forEach(function (word) {
    if (hash[word]) {
      hash[word].forEach(function (match) {
        pairs.push([match, word]);
      });
    }
  });

  return pairs;
}

function findPossiblePalindromePairs(word, hash) {

  // don't add reverse self if word is a palindrome
  // otherwise it will match to itself
  if (!isPalindrome(word)) {
    var wordReversed = reverseWord(word);

    if (!hash[wordReversed]) {
      hash[wordReversed] = [word];
    } else {
      hash[wordReversed].push(word)
    }
  }

  var start = 1; // skip first char
  while (start < word.length) {

    // search for char that matches end char
    if (word[start] === word[word.length - 1]) {

      var palindromeSuffix = word.substring(start, word.length);

      if (isPalindrome(palindromeSuffix)) {
        var prefixReversed = reverseWord(word.substring(0, start))
        if (!hash[prefixReversed]) {
          hash[prefixReversed] = [word];
        } else {
          hash[prefixReversed].push(word)
        }
      }
    }

    start++;
  }
}

function isPalindrome(word) {
  var start = 0;
  var end = word.length - 1;
  while (start < end) {
    if (word.charAt(start) !== word.charAt(end)) {
      return false;
    }
    start++;
    end--;
  }
  return true;
}

function reverseWord(word) {
  var ret = '';
  for (var i = 0; i < word.length; i++) {
    ret = word.charAt(i) + ret;
  }
  return ret;
}

1. For each word, store the reverse of the word and the reverse of that word without the last character, in a hashmap where the value is a list containing the actual word(s)
2. For each word, lookup hashmap and return the current word and list of value attached.
3. Use a hashset for removing duplicates before returning the values

This is one tricky question, okay here is the solution idea and code.

assume you have these input: [bat , tab , tabaa , aatab]

that output should be [ bat , tab ] [ tabaa, bat ] [ bat , aatab ]

step 1: we will store all words as following in hash table as following that has *key as string*
and value as *hash set* let say for strings to make it easier
( but in my code I store only the index of the word )

for word "bat"

b -> { bat }
ba -> { bat }
bat -> { bat }

no we store it also in reverse direction but not reverse string like this

t - > { bat }
at -> { bat }
bat -> { bat } // it will not repeated since its hash set


this operation will take O(NK) where k is the length of maximum word in the input

Step 2: we will iterate through the words again, and for each word we get the reverse of this word
and look in the hash table for the potential string that will cause them to give correct answer.

ex. if we have bat, we will look for "tab" and in the step one we will have in key "tab" 3 strings
which is { tab , tabaa , aatab }

we will check ( battab && tabbat ), ( battabaa & tabaabat ) , ( tabaatab && tabtabaa) and we will
pick the correct ones without repeating ( sure this will cost us another hash set to make sure no
duplicates in output )

here in my code, I used indices rather than store strings, and the output is pair indices for the
2 words.

Sure someone will ask, is the second for loop O( N K ), try your self any sample input, and you
will find that it will never exceed O( N K ) !

bool isPalindrome(const string& w){
	for (int i = 0; i < w.size(); i++){
		if (w[i] != w[w.size() - 1 - i])
			return false;
	}
	
	return true;
}


vector<pair<int, int> > findPalindrome(const vector<string>& words){
	unordered_map<string, unordered_set<int> > wordsMap;
	unordered_set< pair< int, int > > visitedPairs;

	// O( N * K ) where K is the length of the maximum word characters length in the vector
	for (int i = 0; i < words.size(); i++){
		string s;
		string revDirS;

		s.reserve(words[i].size());
		revDirS.reserve(words[i].size());

		for (int j = 0; j < words[i].size(); j++){
                        // ex. tabaa -> t , ta , tab , taba, tabaa
			s += words[i][j];

                        //ex. tabaa -> a , aa , baa , abaa , tabaa  
			revDirS = words[i][words[i].size() - 1 - j] + revDirS; 

			wordsMap[s].insert(i); // saving the indices rather than the words
			wordsMap[revDirS].insert(i);
		}
	}

	vector< pair<int, int> > ret;

	for (int i = 0; i < words.size(); i++){
		string revWord(words[i]);

		reverse(revWord.begin(), revWord.end());

		for (auto wordsIndex : wordsMap[revWord]){

			if (i == wordsIndex)
				continue; 

			int minIndex = min(i, wordsIndex);
			int maxIndex = max(i, wordsIndex);

			if (visitedPairs.count(make_pair(minIndex, maxIndex)) == 0){

				if (isPalindrome(words[i] + words[wordsIndex])){
					ret.push_back(make_pair(i, wordsIndex));
					visitedPairs.insert(make_pair(minIndex, maxIndex));

				}else if (isPalindrome(words[wordsIndex] + words[i])){
					ret.push_back(make_pair(wordsIndex,i));
					visitedPairs.insert(make_pair(minIndex, maxIndex));
				}
			}
		}
	}

	return ret;
}

#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>

using namespace std;

void printPalindromePairs(string words[], unsigned int size) {
	
	unordered_map<string, int> wordMap;
	for (unsigned int i = 0; i < size; i++) {
		string word = words[i];
		reverse(word.begin(), word.end());
		unordered_map<string, int>::iterator it = wordMap.find(word);
		if (it == wordMap.end()) {
			wordMap[words[i]] = i;
		}
		else {
			cout << "FOUND : " << words[i] << ", " << word << endl;
			wordMap.erase(it);
		}
	}
}

int main() {
	
	string words[] = {"bat", "cat", "ami", "tac", "tab"};
	printPalindromePairs(words, 5);
	return 0;

}

My take on this, I assume all words are of same length which is given in the question as k and contain characters from 1 to 256 in ASCII

1. Iterate over the array going through each word. - O(n)
2. For each word make a bitmap using the character set from ASCII - O(k)
3. Store the bitmap created as the key of a HashMap. (If you want, you can store the index of the word as value)
4. While iterating over the next elements , if you find the calculated bit map as a key, then you have found a pair.

Creating the bit map for each word will be O(k) operation and pushing and getting from the HasMap will be O(1) so the total time complexity will come to O(nk).

JavaScript:

var words = ["bat", "tabloid", "cat", "tacoto", "junk", "tab"];
var num = 0;

for (i = 0; i < words.length-1; i++ )
	for (j = i + 1; j < words.length; j++ ){
		num += ispalindrome(words[i], words[j]);
	}

alert (num);

function ispalindrome(word1, word2){
	reverseWord1 = word1.split("").reverse().join("");
	reverseWord2 = word2.split("").reverse().join("");
	
	if ( word1 + word2 == reverseWord2 + reverseWord1 || word2 + word1 == reverseWord1 + reverseWord2 )
		return 1;
	return 0;
}

output: 2

in case, all words are of equal length - solution is simple. We can simply keep inserting the words in a hashset and while inserting a word - we check if reverse of word already exists in set. If it exists, answer is yes and we break, else answer is no when we reach the end of list.

Complexity is when words are of different length. Here is the proposal, ran over several cases and seem to work fine
1. We shall maintain 2 tries - one for original words (trie1) and one for reversed words (trie2).
2. For each word, check if exists in the trie1. If not, insert it in trie1. Also, look for the word in trie2 following it char by char.
a. No match - move on
b. There is a match and you reach the sentinel node by the end - this means 2 words form a palindrome and you can put them in any order.
c. There is a match and either it is non-sentinel node and word is still left. Check if remaining portion is palindrome. If yes, word in trie2 forms the prefix of final palindrome and current word forms the suffix.
3. Reverse each word, check if exists in the trie2. If not, insert it in trie2. Also, look for the word in trie1 following it char by char.
a. No match - move on
b. There is a match and you reach the sentinel node by the end - this means 2 words form a palindrome and you can put them in any order.
c. There is a match and either it is non-sentinel node and word is still left. Check if remaining portion is palindrome. If yes, word in trie1 forms the suffix of final palindrome and current word forms the prefix.

Complexity is O (2kn) since each workd is traversed twice

Should work in O(k * n)...
Basic idea is you go through all Strings and create the possible palindromes.
This is done by reversing the String and checking if substrings of this reversal build a palindrome
with the original String.
(abcb) -> Possible Endings: bcba, cba, a

Furthermore when adding new candidates we cut off parts from the front and check if the rest
is in our palindrome candidates. If the center part is also a palindrome, we have a full palindrome.
(abc) -> Possible Endings: cba
(abc) (dad | cba)

public static String palindromeKN(String[] strs) {
		// Hashtable storing all possible palindrome endings
		Hashtable<String, String> possibleValues = new Hashtable<String, String>();

		for (int i = 0; i < strs.length; i++) {
			String candidate = strs[i];

			// Is our String one of the possible Endings?
			if (possibleValues.containsKey(candidate)) {
				return (possibleValues.get(candidate) + candidate);
			}
			
			
			// Create all possible endings that will lead to a palindrome
			// abcb => bcba, cba, a (go through reverse, cut off a letter and check for palindrome)
			String reverse = new StringBuilder(strs[i]).reverse().toString();
			for (int j = 0; j < reverse.length(); j++) {
				String subString = reverse.substring(j); // cut off first j letters
				if (possibleValues.containsKey(subString)) { // check if this substring is part of the possibilities
					String center = reverse.substring(0, j);
					if (isPalindrome(center)) { // if substring is a possibility, is the rest (what we cut off) also a palindrome?
						return (possibleValues.get(subString) + candidate);
					}
				}
				
				// if the substring is a possible suffix for our candidate add it to hash table
				if (isPalindrome(candidate + subString)) {
					possibleValues.put(subString, candidate);
				}
			}
		}
		return "";
	}
	
	public static boolean isPalindrome(String a) {
		int length = a.length();
		if (length <= 1)
			return true;
		
		for (int i = 0; i < length / 2; i++) {
			if (a.charAt(i) != a.charAt(length - 1 - i)) {
				return false;
			}
		}
		return true;
	}

*Edit* sorry for double post, wasn't logged in...

Should work in O(k * n)...
Basic idea is you go through all Strings and create the possible palindromes.
This is done by reversing the String and checking if substrings of this reversal build a palindrome
with the original String.
(abcb) -> Possible Endings: bcba, cba, a

Furthermore when adding new candidates we cut off parts from the front and check if the rest
is in our palindrome candidates. If the center part is also a palindrome, we have a full palindrome.
(abc) -> Possible Endings: cba
(abc) (dad | cba)

public static String palindromeKN(String[] strs) {
		// Hashtable storing all possible palindrome endings
		Hashtable<String, String> possibleValues = new Hashtable<String, String>();

		for (int i = 0; i < strs.length; i++) {
			String candidate = strs[i];

			// Is our String one of the possible Endings?
			if (possibleValues.containsKey(candidate)) {
				return (possibleValues.get(candidate) + candidate);
			}
			
			
			// Create all possible endings that will lead to a palindrome
			// abcb => bcba, cba, a (go through reverse, cut off a letter and check for palindrome)
			String reverse = new StringBuilder(strs[i]).reverse().toString();
			for (int j = 0; j < reverse.length(); j++) {
				String subString = reverse.substring(j); // cut off first j letters
				if (possibleValues.containsKey(subString)) { // check if this substring is part of the possibilities
					String center = reverse.substring(0, j);
					if (isPalindrome(center)) { // if substring is a possibility, is the rest (what we cut off) also a palindrome?
						return (possibleValues.get(subString) + candidate);
					}
				}
				
				// if the substring is a possible suffix for our candidate add it to hash table
				if (isPalindrome(candidate + subString)) {
					possibleValues.put(subString, candidate);
				}
			}
		}
		return "";
	}
	
	public static boolean isPalindrome(String a) {
		int length = a.length();
		if (length <= 1)
			return true;
		
		for (int i = 0; i < length / 2; i++) {
			if (a.charAt(i) != a.charAt(length - 1 - i)) {
				return false;
			}
		}
		return true;
	}

I have proposed a Trie solution. I don't think O(nk) is an achievable solution. The worst case would be O(n*(k^2)) in the case of {a, aa, aaa, aaaa, aaaaa}.

A detailed Trie structure is proposed and a solution with example is shown as well. Follow this for more details: cpluspluslearning-petert.blogspot.co.uk/2015/05/data-structure-and-algorithm-trie-and.html

Check my analysis for this problem: allenlipeng47.com/PersonalPage/index/view/166/nkey

public static boolean isPalindrome(String inputString) {
    if (inputString.length() == 0 || inputString.length() == 1) {
        return true;
    }
    boolean currentSame = inputString.charAt(0) == inputString.charAt(inputString.length() - 1);
    String remaining = inputString.substring(1, inputString.length() - 1);
    return (same && isPalindrome(remaining));
}

public static class Pair<F, S> {
    F first;
    S second;

    public Pair(F first, S second) {
        this.first = first;
        this.second = second;
    }
}

public static List<Pair<String, String>> getPalindromes(List<String> inputList) {
    Set<String> inputSet = new HashSet<>();
    inputSet.addAll(inputList);
    for (String current : inputList) {
        StringBuilder sb = new StringBuilder(current);
        String reverse = sb.reverse().toString();
        for (int i = 0; i < reverse.length(); i++) {
            String currentReverse = reverse.substring(i);
            if (stringSet.contains(currentReverse)) {
                if (isPalindrome(current + currentReverse)) {
                    returnList.add(new Pair(current, currentReverse));
                }
            }
        }
    }
    return returnList;
}

How about this:
Maintain a trie of words like following:
For each word:
1) Check if reverse of it is already present in trie:
--> Already present: The pair is found. print the pair.
--> Partially present: either new word is longer or existing word is longer. Check is remaining part is palindrome. If yes, your pair is found, print the pair.

2) Add the word to trie.

e.g. input array ["abcd", "cba", "a", "ta", "bc", .... .... ....]
1) check if reverse of "abcd" is in trie ---- no
2) enter "abcd" in try
3) check if reverse of "abc" i.e. "cba" is in trie - yes partially, remaining "d" is palindrome - print the pair.
4) enter "abc" in trie..
5) check reverse of "a" in trie.. will partially match with "abcd", but remaining "bcd" is not palindrome - NO match
6) enter "a" in palindrome
7) check reverse "ta" ... matches with "a" and "t" is remaining... hence match - print pair.
.. similarly for "ba" and so on...

complexity should be N times O(K) where N is number of words... K is len of max size word

Runtime can't better better than O(n^2).

Proof: generate a set such that any pair would make a palindrome (easy). This means the #results = n^2. If your algorithm has less than n^2, it's not likely that it'll produce enough results.

With that in mind, keep it simple: use 2 loops but using other tricks to quickly check if a pair can make a palindrome or not.

test

Here is the solution using trie

public class PairOfPalindrome {

    static class ResultHelper {
        public int index1, index2;


        public ResultHelper(int index1, int index2) {
            this.index1 = index1;
            this.index2 = index2;
        }

        @Override
        public String toString() {
            return "{" +
                    "index1=" + index1 +
                    ", index2=" + index2 +
                    '}';
        }
    }

    static class TrieNode {

        public boolean isLeaf = false;
        public Map<Character, TrieNode> children = new HashMap<>();
        public List<Integer> palindromsWithinString = new ArrayList<>();
        public int idOfThisString = -1;
    }

    static class Trie {

        TrieNode root;

        void insert(String toInsert, int myId) {
            if (root == null)
                root = new TrieNode();

            TrieNode pCrawl = root;

            for (int i = toInsert.length() - 1; i >= 0; i--) {

                char currentChar = toInsert.charAt(i);

                if (!pCrawl.children.containsKey(currentChar))
                    pCrawl.children.put(currentChar, new TrieNode());


                if (isPalindrome(toInsert, 0, i))
                    pCrawl.palindromsWithinString.add(myId);

                pCrawl = pCrawl.children.get(currentChar);


            }
            pCrawl.isLeaf = true;
            pCrawl.idOfThisString = myId;


        }

        private boolean isPalindrome(String toInsert, int from, int to) {

            while (from < to && toInsert.charAt(from) == toInsert.charAt(to)) {
                from++;
                to--;
            }

            if (from == to)
                return true;
            return false;
        }

        public List<ResultHelper> search(String toSearch, int myId) {

            List<ResultHelper> resultHelpers = new ArrayList<>();
            if (search(toSearch, myId, resultHelpers))
                return resultHelpers;
            else
                return Collections.EMPTY_LIST;

        }

        private boolean search(String toSearch, int myId, List<ResultHelper> resultHelpers) {
            if (null == root)
                return false;


            TrieNode pCrawl = root;

            for (int i = 0; i < toSearch.length(); i++) {

                char currentChar = toSearch.charAt(i);

                if (!pCrawl.children.containsKey(currentChar))
                    return false;

                pCrawl = pCrawl.children.get(currentChar);

                if (pCrawl.idOfThisString >= 0 && pCrawl.idOfThisString != myId
                        && isPalindrome(toSearch, i, toSearch.length() - 1)) {
                    resultHelpers.add(new ResultHelper(myId, pCrawl.idOfThisString));

                }


            }

            for (int rem : pCrawl.palindromsWithinString) {
                resultHelpers.add(new ResultHelper(myId, rem));
            }

            return true;
        }


    }

    public static void main(String args[]) {

        String[] list = {"abc", "xyxcba", "geekst", "or", "keeg", "bc"};

        Trie trie = new Trie();
        for (int i = 0; i < list.length; i++)
            trie.insert(list[i], i);

        for (int i = 0; i < list.length; i++) {
            List<ResultHelper> result = trie.search(list[i], i);
            if (!result.isEmpty())
                System.out.println(result);
        }


    }

}

JavaScript solution, tested on jsfiddle.net/jacklehamster/j5qbharr
Not 100% sure it's O(nk) though. It kinda looks like O(n * k^2)

function findPalinPair(array) {
    
    function flip(str) {
        return str.split("").reverse().join("");
    }
    
    function isPalin(str) {
        for(var i=0;i<str.length/2;i++) {
            if(str.charAt(i)!=str.charAt(str.length-1-i)) {
                return false;
            }
        }
        return true;
    }
    
    //    hash will store all the possible matches
    var hash = {};
    var wordsSeen = {};
    
    for(var i=0;i<array.length;i++) {
        var word = array[i];
        wordsSeen[word] = true;
        if(hash[word]) {
            return isPalin(word+hash[word])?[word,hash[word]]:[hash[word],word];
        }
        
        // first reverse the entry (tacoto=>otocat)
        var rev = flip(word);
        // we know that the reverse would be a match. (tacotootocat)
        hash[rev] = word;
        // some substrings of the reverse (like "cat") are also match
        for(var j=1;j<rev.length-1;j++) {
            var splitLeft = rev.slice(0,j);
            var splitRight = rev.slice(j);
            if(isPalin(splitLeft + word)) {
                if(wordsSeen[splitLeft]) {
                    return [splitLeft,word];
                }
                hash[splitLeft] = word;
            }
            if(isPalin(word + splitRight)) {
                if(wordsSeen[splitRight]) {
                    return [word,splitRight];
                }
                hash[splitRight] = word;
            }
        }
    }
    return null;
}


function test(array) {
    var result = findPalinPair(array);
    document.body.innerHTML += (result?result.join("-"):"nothing") + "<br>";
}

test(["bat","tab","cat","junk"]); // bat-tab
test(["bat","tabloid","cat","junk"]);    //    null
test(["bat","tabloid","cat","ototac","junk"]);    // cat-ototac
test(["bat","tabloid","cat","tacoto","junk"]);    // tacoto-cat
test(["tacoto","bat","tabloid","cat","junk"]);    // tacoto-cat

//    Test with a bunch of random numbers
function testNumber() {
    var array = [];
    for(var i=0;i<100000;i++) {
        array.push(""+Math.floor(Math.random()*100000000));
    }
    test(array);
}

for(var i=0;i<10;i++) testNumber();

test

Flip inversion may help in Mergesort

Sorry... it won't help.. I was wrong

form a list which contains the original words and reverse of each of the word, the size of this new list will be twice the original, perform lexicographic sorting on this list, compare adjacent words, if a word appears twice we get a palindrome, at the end divide the number of such palindromes found by 2 .
like
{bat,tab,cat} reverse list={tab,bat,tac} after meging these two and lexicographic sorting we get
{bat,bat,cat,tab,tab,tac}
we get 2 such pairs (bat,bat) and (tab,tab)
2/2 =1 overall (removing double count)

As we find a single pair of word we get the answer, right? Or we need to find the number of pair of words? Although worst case complexity will remain same...

Answer:
Can we do it like this?
Create a Hashset of these words.
Then take an iterator from this HashSet. Take out each word and find if the reverse is there in the HashSet. If found remove both of them and go on like this.
reversing a word takes O(k) time.

all words are in equal length of k OR different lengths?

public class Palindrome {

public static String reverse(String A) {
String reverse = "";
for (int i = A.length()-1; i >= 0; i--) {
reverse = reverse + A.charAt(i);
}
return reverse;
}

public static void main(String[] args) {
String[] s = { "bat", "tab", "cat", "tac", "deepak", "garg" };
Map<String, String> wordReverseMap = new HashMap<String, String>();

for (int i = 0; i < s.length; i++) {
if (wordReverseMap.containsKey(s[i])) {
System.out.println(s[i] + " " + wordReverseMap.get(s[i]));
} else {
wordReverseMap.put(Palindrome.reverse(s[i]), s[i]);
}
}
}
}

public class Palindrome {

	public static String reverse(String A) {
		String reverse = "";
		for (int i = A.length()-1; i >= 0; i--) {
			reverse = reverse + A.charAt(i);
		}
		return reverse;
	}

	public static void main(String[] args) {
		String[] s = { "bat", "tab", "cat", "tac", "deepak", "garg" };
		Map<String, String> wordReverseMap = new HashMap<String, String>();

		for (int i = 0; i < s.length; i++) {
			if (wordReverseMap.containsKey(s[i])) {
				System.out.println(s[i] + " " + wordReverseMap.get(s[i]));
			} else {
				wordReverseMap.put(Palindrome.reverse(s[i]), s[i]);
			}
		}
	}
}