1
// 149ms
2

3
class Solution {
4
  public List<List<Integer>> palindromePairs(String[] words) {
5
    HashMap<String, Integer> wordMap = new HashMap<>();
6
    Set<Integer> set = new TreeSet<>();
7
    int n = words.length;
8

9
    for (int i = 0; i < n; i++) {
10
      wordMap.put(words[i], i);
11
      set.add(words[i].length());
12
    }
13

14
    List<List<Integer>> ans = new ArrayList<>();
15

16
    for (int i = 0; i < n; i++) {
17
      int length = words[i].length();
18

19
      // if(length ==1){
20
      //     if(wordMap.containsKey("")){
21
      //         ans.add(Arrays.asList(i, wordMap.get("")));
22
      //         ans.add(Arrays.asList(wordMap.get(""), i));
23
      //     }
24
      //     continue;
25
      // }
26
      String reverse = new StringBuilder(words[i]).reverse().toString();
27
      if (wordMap.containsKey(reverse) && wordMap.get(reverse) != i)
28
        ans.add(Arrays.asList(i, wordMap.get(reverse)));
29

30
      for (Integer k : set) {
31
        if (k == length) break;
32
        if (isPalindrome(reverse, 0, length - 1 - k)) {
33
          String s1 = reverse.substring(length - k);
34
          if (wordMap.containsKey(s1)) ans.add(Arrays.asList(i, wordMap.get(s1)));
35
        }
36

37
        if (isPalindrome(reverse, k, length - 1)) {
38
          String s2 = reverse.substring(0, k);
39
          if (wordMap.containsKey(s2)) ans.add(Arrays.asList(wordMap.get(s2), i));
40
        }
41
      }
42
    }
43
    return ans;
44
  }
45

46
  private boolean isPalindrome(String s, int left, int right) {
47
    while (left < right) if (s.charAt(left++) != s.charAt(right--)) return false;
48
    return true;
49
  }
50
}