> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/trie-tree/336.palindrome-pairs.md).

# 336.Palindrome-Pairs

## 336. Palindrome Pairs

## 题目地址

<https://leetcode.com/problems/palindrome-pairs/>

## 题目描述

```
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:
Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]
```

## 代码

### Approach #1 Brute force

Time Complexity : `O(n^2*k)` // and k be the length of the longest word.

```java
class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> pairs = new ArrayList();
    for (int i = 0; i < words.length; i++) {
      for (int j = 0; j < words.length; j++) {
        if (i == j)     continue;
        String combined = words[i].concat(words[j]);
        String reversed = new StringBuilder(combined).reverse().toString();
        if (combined.equals(reversed)) {
          pairs.add(Arrays.asList(i, j));
        }
      }
    }

    return pairs;
  }
}
```

### Approach #2 Hashing

Time: `O(k^2 * n)` Space: `O((k+n)^2)`

Three Cases:

1. Check if the reverse of **word** is present. If it is, then we have a **case 1** pair by appending the reverse onto the end of **word**.
2. For each **suffix** of **word**, check if the **suffix** is a palindrome. **if it is a palindrome**, then reverse the remaining **prefix** and check if it's in the list. If it is, then this is an example of **case 2**.
3. For each **prefix** of **word**, check if the **prefix** is a palindrome. **if it is a palindrome**, then reverse the remaining **suffix** and check if it's in the list. If it is, then this is an example of **case 3**.

```java
class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
    Map<String, Integer> wordSet = new HashMap<>();
    for (int i = 0; i < words.length; i++) {
      wordSet.put(words[i], i);
    }

    List<List<Integer>> solution = new ArrayList();
    for (String word: wordSet.keySet()) {
      int currentWordIndex = wordSet.get(word);
      String reversedWord = new StringBuilder(word).reverse().toString();
      // case #1
      if (wordSet.containsKey(reversedWord) 
          && wordSet.get(reversed) != currentWordIndex) {

        solution.add(Arrays.asList(currentWordIndex, wordSet.get(reversedWord)));
      } 
      // case #2
      for (String suffix: allValidSuffixes(word)) {
        String reversedSuffix = new StringBuilder(suffix).reverse().toString();
        if (wordSet.containsKey(reversedSuffix)) {
          solution.add(Arrays.asList(wordSet.get(reversedSuffix), currentWordIndex));
        }
      }

      // case #3
      for (String prefix: allValidPrefixed(word)) {
        String reversedPrefix = new StringBuilder(prefix).reverse().toString();
        if (wordSet.containsKey(reversedPrefix)) {
          solution.add(Arrays.asList(currentWordIndex, wordSet.get(reversedPrefix)));
        }
      }
    }

    return solution;
  }

   private List<String> allValidPrefixes(String word) {
        List<String> validPrefixes = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            if (isPalindromeBetween(word, i, word.length() - 1)) {
                validPrefixes.add(word.substring(0, i));
            }
        }
        return validPrefixes;
    }

    private List<String> allValidSuffixes(String word) {
        List<String> validSuffixes = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            if (isPalindromeBetween(word, 0, i)) {
                validSuffixes.add(word.substring(i + 1, word.length()));
            }
        }
        return validSuffixes;
    }

     // Is the prefix ending at i a palindrome?
    private boolean isPalindromeBetween(String word, int front, int back) {
        while (front < back) {
            if (word.charAt(front) != word.charAt(back)) return false;
            front++;
            back--;
        }
        return true;
    }

}
```

### Approach #3 Using a Trie

```java
class TrieNode {
  public int wordEnding = -1;
  public Map<Character, TrieNode> next = new HashMap();
  public List<Integer> palindromePrefixRemaining = new ArrayList();
}

class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
    TrieNode trie = new TrieNode();

    // 1. build the Trie with reversed words
    for (int wordId = 0; wordId < words.length; wordId++) {
      String word = words[wordId];
      String reversedWord = new StringBuilder(word).reverse().toString();
      TrieNode currentTrieLevel = trie;
      for (int j = 0; j < reversedWord.length(); j++) {
        if (hasPalindromeRemaining(reversedWord, j)) {
          currentTrieLevel.palindromePrefixRemaining.add(wordId);
        }
        Character c = reversedWord.charAt(j);
        if (!currentTrieLevel.next.containsKey(c)) {
          currentTrieLevel.next.put(c, new TrieNode());
        }
        currentTrieLevel = currentTrieLevel.next.get(c);
      }
      currentTrieLevel.wordEnding = wordId;
    }

    // 2. Find Pairs
    List<List<Integer>> pairs = new ArrayList<>();
    for (int wordId = 0; wordId < words.length; wordId++) {
      String word = words[wordId];
      TrieNode currentTrieLevel = trie;
      for (int j = 0; j < word.length(); j++) {
        // case #3:  word:(xxx + Palindrome), trie: xxx
        if (currentTrieLevel.wordEnding != -1
           && hasPalindromeRemaining(word, j)) {
          pairs.add(Arrays.asList(wordId, currentTrieLevel.wordEnding));
        }

        Character c = word.charAt(j);
        currentTrieLevel = currentTrieLevel.next.get(c);
        if (currentTrieLevel == null)        break;
      }

      if (currentTrieLevel == null) continue;

      // case #1
      if (currentTrieLevel.wordEnding != -1 
          && currentTrieLevel.wordEnding != wordId) {
        pairs.add(Arrays.asList(wordId, currentTrieLevel.wordEnding));
      }

      // case #2: Trie:(Palindrome + xxx) , word:xxx
      for (int other: currentTrieLevel.palindromePrefixRemaining) {
        pairs.add(Arrays.asList(wordId, other));
      }
    }

    return pairs;
  }

  private boolean hasPalindromeRemaining(String s, int i) {
    int p1 = i;
    int p2 = s.length() - 1;
    while (p1 < p2) {
      if (s.charAt(p1) != s.charAt(p2))        return false;
      p1++;
      p2--;
    }
    return true;
  }
}
```