# 107ms AC Java Solution-Time Complexity is O(N*K)--N is size of words, K is avg length of a word

• ``````public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res =new ArrayList<>();
if(words == null|| words.length <2)
return res;

Map<String,Integer> word_idx = new HashMap<>();

for( int i = 0 ; i< words.length ; i++)
word_idx.put(words[i], i);

for (int i = 0; i < words.length; i++) {
String aWord = words[i];
if (aWord.length() > 0) {
if (!isPalindrome(aWord, 0, aWord.length() - 1)) {

String comple = reverseLetters(aWord, 0, aWord.length() - 1);

if (word_idx.containsKey(comple)) {
List<Integer> aCombo = new ArrayList<>();
}

} else {
String comple = "";
if (word_idx.containsKey(comple)) {
List<Integer> aCombo = new ArrayList<>();
aCombo.set(0, aCombo.set( 1,aCombo.get(0) ) );
}
}

for (int j = 0; j < aWord.length(); j++) {

if (j + 1 < aWord.length() && isPalindrome(aWord, 0, j)) {
String comple = reverseLetters(aWord, j + 1,
aWord.length() - 1);

if (word_idx.containsKey(comple)) {
List<Integer> aCombo = new ArrayList<>();
}

}

if (0 < j && j < aWord.length()
&& isPalindrome(aWord, j, aWord.length() - 1)) {

String comple = reverseLetters(aWord, 0, j - 1);

if (word_idx.containsKey(comple)) {
List<Integer> aCombo = new ArrayList<>();
}

}
}
}
}

return res;
}

private boolean isPalindrome(String aWord, int start, int end){

if(end == start ) return true;

int mid = (end+start+1)/2;

for(int i = start ; i < mid ; i ++){
if(aWord.charAt(i) != aWord.charAt(end+start-i))
return false;
}

return true;
}

private String reverseLetters(String s , int start, int end){
if(end == start) return String.valueOf(s.charAt(end));
StringBuffer sb = new StringBuffer();

for( int i = end ; i>= start ; i--)
sb.append(s.charAt(i));

return sb.toString();
}``````

• It is O(n*k^2)

• you are right, it is O(NKK)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.