336. Palindrome Pairs

題目網址：https://leetcode.cn/problems/palindrome-pairs/

題意：給一單字互不相同的 string list words, 找出所有不同的 index pair (i, j), 使得 word[i] + word[j] 為迴文。

Solution 1：（TLE 無法通過）

想法：利用 Trie

• 首先, 我們把所有 words[i] 給 insert 到 trie 中

• 若 string words[i] 存在迴文 pair, 則可以先將 words[i] 拆成 s1 和 s2, 也就是說 words[i] = s1 + s2

  • 若 s1 的部分為迴文, 假設 words[i] = XXXXabc, 其中 s1 = XXXX 表示為迴文, s2 = abc。若存在迴文, 則應存在 left = reverse(s2) = cba, 使得 left + words[i] = cbaXXXXabc 為迴文, 得到迴文 pair 為 {leftIdx, i}
  • 若 s2 的部分為迴文, 假設 words[i] = abcXXXX, 其中 s2 = XXXX 表示為迴文, s1 = abc。若存在迴文, 則應存在 right = reverse(s1) = cba, 使得 words[i] + right = abcXXXXcba 為迴文, 得到迴文 pair 為 {i, rightIdx}

• 若有一 word[i] = "aaa", 當 s1 = "", s2 = "aaa" = reverse(s2), 到 trie 中找到的 idx 會是自己的 idx i, 因此要滿足 idx != -1 && idx != i 才能新增迴文 pair

• 當 words[i] = ["a", ""], for loop 中 0 ≤ j ≤ words[i].size(), 這樣 "" 才會被 insert 到 trie 中

  

• 若 words = ["abcd", "dcba"], words[i] 恰存在 words[j], 使得 words[i] == reverse(words[j]), 會得到重複的迴文 pair, 也就 0 ≤ j ≤ words[i].size() 中等號只取一次, 否則會有重複的答案, 這邊我們設 j == 0 時不判斷 s1 是否為迴文

  

class TrieNode{
public:
    TrieNode* children[26] = {nullptr};
    int idx = -1; // 每個 word 的 end node 會紀錄 word 在 words 中的 idx
};

class Trie{
public:
    TrieNode* root;

    Trie() : root(new TrieNode()) {}

    // 如果為 empty string, 則會修改 root->idx
    void insert(const string& word, const int idx){
        TrieNode *node = root;

        for (const auto& ch : word) {
            const int i = ch - 'a';
            if (!node->children[i]) {
                node->children[i] = new TrieNode();
            }
            node = node->children[i];
        }

        node->idx = idx;
    }

    // 如果 trie 中存在 s, 則返回 end node 之 idx
    int find(const string& s){
        TrieNode *node = root;

        for (const auto& ch : s) {
            const int i = ch - 'a';
            if (!node->children[i]) {
                return -1;
            }
            node = node->children[i];
        }

        return node->idx;
    }
};

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        for (int i = 0; i < words.size(); ++i) {
            trie.insert(words[i], i);
        }

        vector<vector<int>> res;
        for (int i = 0; i < words.size(); ++i) {
            const auto& w = words[i];

            // j 是 <= words[i], 因為 empty string 也算迴文
            for (int j = 0; j <= w.size(); ++j) {
                // 若 s1 為迴文, 則到 trie 中尋找是否有 reverse(s2)
                // 0 <= j <= w.size() 只取一次, 否則會有重複的答案
                if (j != 0 && isPalindrome(w, 0, j - 1)) {
                    const auto s2 = w.substr(j);
                    reverse(s2.begin(), s2.end());
                    const int leftIdx = trie.find(s2);

                    if (leftIdx != -1 && leftIdx != i) {
                        res.emplace_back(vector<int>{leftIdx, i});
                    }
                }

                // 若 s2 為迴文, 則到 trie 中尋找是否有 reverse(s1)
                if (isPalindrome(w, j, w.size() - 1)) {
                    const auto s1 = w.substr(0, j);
                    reverse(s1.begin(), s1.end());
                    const int rightIdx = trie.find(s1);

                    if (rightIdx != -1 && rightIdx != i) {
                        res.emplace_back(vector<int>{i, rightIdx});
                    }
                }
            }
        }
        return res;
    }

private:
    Trie trie;

    bool isPalindrome(const string& s, int left, int right){
        while (left < right) {
            if (s[left++] != s[right--]) {
                return false;
            }
        }
        return true;
    }
};

• time：$O(n\cdot m^2)$ ➔ 其中 $n$ 為 word 的個數, $m$ 是 word 的平均長度
  • $O(m^2)$：判斷一個 word 中所有的 s1 和 s2 是否為迴文, 總共有 $m$ 種不同的 s1 和 s2, 每判斷一種 s1 和 s2 是否為迴文、到 trie 查找皆需花 $O(m)$
• space：$O(n\cdot m)$ ➔ trie, worse case：每個 word 的 prefix 皆不重複

---

Solution 2：（TLE 無法通過）

想法：利用 hash table, 同 Solution 1, 只是存到 hash table 中

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        const int n = words.size();
        unordered_map<string, int> idx;

        for (int i = 0; i < n; ++i) {
            idx[words[i]] = i;
        }

        vector<vector<int>> res;
        for (int i = 0; i < n; ++i) {
            const auto& w = words[i];

            // j 是 <= words[i], 因為 empty string 也算迴文
            for (int j = 0; j <= w.size(); ++j) {
                // 若 s1 為迴文, 則到 hast table 中尋找是否有 reverse(s2)
                // 0 <= j <= w.size() 只取一次, 否則會有重複的答案
                if (j != 0 && isPalindrome(w, 0, j - 1)) {
                    const auto s2 = w.substr(j);
                    reverse(s2.begin(), s2.end());
                    const auto left = idx.find(s2);
                    if (left != idx.end() && left->second != i) {
                        res.emplace_back(vector<int>{left->second, idx[w]});
                    }
                }

                // 若 s2 為迴文, 則到 hash table 中尋找是否有 reverse(s1)
                if (isPalindrome(w, j, w.size() - 1)) {
                    const auto s1 = w.substr(0, j);
                    reverse(s1.begin(), s1.end());
                    const auto right = idx.find(s1);
                    if (right != idx.end() && right->second != i) {
                        res.emplace_back(vector<int>{idx[w], right->second});
                    }
                }
            }
        }
        return res;
    }

private:
    bool isPalindrome(const string& s, int left, int right){
        while (left < right) {
            if (s[left++] != s[right--]) {
                return false;
            }
        }
        return true;
    }
};

• time：$O(n\cdot m^2)$ ➔ 其中 $n$ 為 word 的個數, $m$ 是 word 的平均長度
  • $O(m^2)$：判斷一個 word 中所有的 s1 和 s2 是否為迴文, 總共有 m 種不同的 s1 和 s2, 每判斷一種 s1 和 s2 是否為迴文需花 $O(m)$
• space：$O(n\cdot m)$ ➔ hash table 需保存 string 和對應的 idx, 總共 n 個 word, 每個 word 平均長度為 m