解題說明
Palindrome Pairs
題目描述：給定一個字串陣列 words（所有字串均不重複），找出所有下標對 (i, j)（i ≠ j），使得 words[i] + words[j] 拼接後為回文串，返回所有這樣的對。
解題思路：先將所有字串的「反轉」存入 hash map（reversed_word → index）。對每個字串 words[i]，嘗試所有分割點 k（0 到 len）把它分成前綴 prefix = words[i][0..k-1] 和後綴 suffix = words[i][k..len-1]：
- 若 prefix 本身是回文，且 reverse(suffix) 存在於 map（設為索引 j，且 j ≠ i），則 words[j] + words[i] 是回文對，記錄 (j, i)。
- 若 suffix 本身是回文，且 reverse(prefix) 存在於 map（設為索引 j，且 j ≠ i），則 words[i] + words[j] 是回文對，記錄 (i, j)。
注意 k = 0 和 k = len 的邊界：為避免重複，當 suffix 為空時（k = len），只做前綴是回文的那種檢查；實作上限制其中一個分支不在 suffix 為空時執行即可。
C++ 解法
複雜度分析
時間複雜度：O(n × k²)，其中 n 為字串數量，k 為字串平均長度 — 對每個字串有 O(k) 個分割點，每次 substr 和 isPalindrome 各 O(k)，hash map 查詢含字串 hash O(k)，故每個字串耗時 O(k²)，整體 O(n k²)。
空間複雜度：O(n × k) — hash map 存儲 n 個反轉字串，每個長度 k；結果陣列最多 O(n²) 對。
虛擬碼
1. Build revMap: for each word[i], store (reverse(word[i]) -> i).
2. For each word[i] with length len:
a. For each split point k from 0 to len:
- prefix = word[i][0..k-1], suffix = word[i][k..len-1].
- Case 1: if isPalindrome(prefix) and revMap has suffix with index j != i:
add [j, i] to result.
- Case 2: if k < len and isPalindrome(suffix) and revMap has prefix with index j != i:
add [i, j] to result.
3. Return result.
isPalindrome(s): two-pointer check from both ends.其他解法
方法一：Hash Map + 分割枚舉（本題主解）O(n k²) 儲存各字串的反轉，對每個字串枚舉 O(k) 個分割點，判斷前綴/後綴是否為回文後查表。時間 O(n k²)，空間 O(n k)，實作直觀。
方法二：Trie + 回文判斷 O(n k²) 將所有字串的反轉建入 Trie。對每個字串沿 Trie 走，若走到葉節點且剩餘部分是回文，則找到一對；若 Trie 節點標記某個字串且該字串剩餘部分是回文，也找到一對。最壞時間複雜度相同，但 Trie 在字首共享時可省略重複計算，空間 O(n k)。
方法三：暴力比對 O(n² k) 對所有 (i, j) 對直接拼接並判斷是否回文。n² 對，每次 O(k)，總體 O(n² k)。當 n 較小時可接受，但通常 TLE。
延伸思考
- 本題假設所有字串互不相同；若允許重複字串（如 ["a", "a"]），演算法需要做哪些修改以正確去重或計數？
- 若要進一步優化 isPalindrome 的呼叫次數，可以預計算每個字串所有前綴和後綴是否為回文，請說明如何使用 Manacher's Algorithm 達成此目的。
- 若改用 Trie 實作，相較 hash map 方法在哪種輸入分布下有明顯優勢？