> 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;
  }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/trie-tree/336.palindrome-pairs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.