# 300ms Java solution

• Thanks to Nursike's answer, brilliant thought by scanning continuous part of each word, so that only need to check the rest part rather than the whole combination word.

public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (words == null || words.length == 0) return ret;
int n = words.length - 1;
Map<String, Integer> wordsMap = new HashMap<String, Integer>(); //  store all words and corresponding indexes
for (int i = 0; i < words.length; i++) {
wordsMap.put(words[i], i);
}
/** brutal force: TLE */
// Set<String> palindromes = new HashSet<String>();
// for (int i = 0; i < n-1; i++) {
// for (int j = i+1; j < n; j++) {
//     String frontEnd = words[i] + words[j];
//     String endFront = words[j] + words[i];
//     List<Integer> cur;
//     if (palindromes.contains(frontEnd) || isPalindrome(frontEnd)) {
//     }
//     if (palindromes.contains(endFront) || isPalindrome(endFront)) {
//     }
// }
// }

for (int i = 0; i < words.length; i++) {
/* notice that left/right, only one of them should
* cover the whole word, otherwise the whole will
* be checked twice */

/* if word[i]:(abc)de + word[j]:cba, only need to check whether "de" is palindrome */
for (int right = 0; right <= words[i].length(); right++) {
String leftSymmetric = words[i].substring(0, right);
Integer j = wordsMap.get(new StringBuffer(leftSymmetric).reverse().toString());
if (j == null || i == j) {
continue;
}
if (isPalindrome(words[i].substring(right))) {
}
}
/* if word[j]:ed + word[i]:abc(de), only need to check whether "abc" is palindrome */
for (int left = words[i].length(); left >= 1; left--) { //  here left >= 1 because the whole word has been checked
//  in the right part
String rightSymmetric = words[i].substring(left);
Integer j = wordsMap.get(new StringBuffer(rightSymmetric).reverse().toString());
if (j == null || i == j) {
continue;
}
if (isPalindrome(words[i].substring(0, left))) {
}
}

}
return ret;
}
private boolean isPalindrome(String word) {
for (int i = 0, j = word.length()-1; i < j; i++, j--) {
if (word.charAt(i) != word.charAt(j)) {
return false;
}
}
return true;
}

• This post is deleted!

• this maybe have duplicate arrarylist so need to use the HashSet to store then toArrayList

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