如何利用Trie数据结构解决Palindrome Pairs（回文对）问题？

Let's walk through exactly how to leverage a Trie (prefix tree) to efficiently find all index pairs (i,j) where words[i] + words[j] is a palindrome. I'll break this down with plain logic, Trie design, and step-by-step examples to make it concrete.

Core Intuition #

First, let's recap what makes word1 + word2 a palindrome:

• Either reverse(word2) is a prefix of word1, and the remaining part of word1 (after this prefix) is a palindrome. For example: if word1 = "abcdd" and word2 = "cba", reverse(word2) = "abc" is a prefix of word1, and the remaining "dd" is a palindrome. So "abcdd" + "cba" = "abcddcba" which is a palindrome.
• Or reverse(word1) is a prefix of word2, and the remaining part of word2 (after this prefix) is a palindrome. For example: if word1 = "cba" and word2 = "ddabc", reverse(word1) = "abc" is a prefix of word2, and the remaining "dd" is a palindrome. So "cba" + "ddabc" = "cbaddabc" which is a palindrome.

A Trie helps us quickly look up these prefixes and track the necessary metadata to validate the palindrome condition without brute-forcing every possible pair.

Trie Node Structure #

We'll need a custom Trie node with three key components:

• children: A dictionary mapping characters to child nodes (standard for Tries).
• word_index: Stores the index of the original word if this node marks the end of a reversed word (so we can quickly get which word matches the prefix).
• palindrome_suffix_indices: A list of indices of reversed words where the remaining part (after the current prefix) is a palindrome. This helps us handle the second case above efficiently.

Step 1: Build the Trie with Reversed Words #

First, we insert the reverse of every word into the Trie. As we insert each reversed word, we do two critical things:

1. At each node along the insertion path, check if the remaining substring (of the reversed word) is a palindrome. If yes, add the original word's index to that node's palindrome_suffix_indices list.
   • For example, inserting reversed word "tab" (original word "bat" at index 0):
     • When we reach the 't' node, remaining substring is "ab" (not a palindrome, no addition).
     • When we reach the 'a' node, remaining substring is "b" (not a palindrome, no addition).
     • When we reach the 'b' node, remaining substring is "" (which is a palindrome), so add index 0 to the 'b' node's palindrome_suffix_indices.
2. When we reach the end of the reversed word, set the node's word_index to the original word's index.

Step 2: Traverse Each Word to Find Valid Pairs #

For each word word (at index i), we traverse its characters in the Trie to find valid pairs:

Case 1: Found a reversed word that is a prefix of word #

As we traverse each character of word:

• If we hit a node with a non-null word_index (let's call this index j), check if the remaining part of word (after the current prefix) is a palindrome. If yes, then (i, j) is a valid pair because word + words[j] will be a palindrome.
  • Using your example words = ["bat", "tab", "cat"]:
    • When traversing "bat" (index 0), we reach the 't' node (from reversed "tab" which maps to index 1). The remaining part of "bat" is empty (a palindrome), so we add [0, 1] to the result.

Case 2: The word is a prefix of some reversed words with palindromic suffixes #

Once we finish traversing all characters of word, we look at the current node's palindrome_suffix_indices list. Each index j in this list represents a word where reverse(words[j]) starts with word, and the remaining part of words[j] is a palindrome. So (i, j) is a valid pair.

• For example, if we have a word "a" and another word "aaa", reversed "aaa" is "aaa". When inserting "aaa", the nodes for 'a' (remaining "aa" which is palindrome), 'aa' (remaining "a" which is palindrome), and 'aaa' (remaining "" which is palindrome) will all have the index of "aaa" in their palindrome_suffix_indices. When traversing "a", after reaching the 'a' node, we add the index of "aaa" to get the pair (i, j) where "a"+"aaa"="aaaa" is a palindrome.

Edge Case: Handle Empty String #

If the input includes an empty string "", any palindrome word w will form pairs (index_of_w, index_of_empty) and (index_of_empty, index_of_w) since w+"" and ""+w are both palindromes. This is naturally handled by our Trie logic (since reversed empty string is empty, inserting it sets a node's word_index to its index, and when traversing a palindrome word, the remaining part after empty prefix is the word itself which is a palindrome).

Example Walkthrough (From Your Question) #

Let's take words = ["bat", "tab", "cat"] (indices 0,1,2):

1. Build Trie with reversed words:
   • Reversed words are "tab" (0), "bat" (1), "tac" (2).
   • Insert "tab": Nodes t -> a -> b. b node has word_index=0, and palindrome_suffix_indices=[0].
   • Insert "bat": Nodes b -> a -> t. t node has word_index=1, and palindrome_suffix_indices=[1].
   • Insert "tac": Nodes t -> a -> c. c node has word_index=2, and palindrome_suffix_indices=[2].
2. Traverse each word:
   • For "bat" (0):
     • Traverse b -> a -> t. The t node has word_index=1. Remaining part is empty (palindrome), so add [0,1].
   • For "tab" (1):
     • Traverse t -> a -> b. The b node has word_index=0. Remaining part is empty (palindrome), so add [1,0].
   • For "cat" (2):
     • Traverse c -> a -> t. No nodes along the way have word_index except the end (which is its own index, and we skip pairs where i=j per unique word rules). The t node's palindrome_suffix_indices is empty, so no new pairs.
3. Final result: [[0,1], [1,0]] which matches the example.

Why This Works Efficiently #

Using a Trie reduces the time complexity compared to brute-force (which is O(n²*k) where n is number of words and k is average word length). With Trie, we get O(n*k²) time—since inserting each reversed word takes O(k) time, and for each word, traversing takes O(k) time plus checking palindromes for remaining substrings (which is O(k) per check, hence O(k²) per word).

内容的提问来源于stack exchange，提问作者Neha Singh