336.回文對

題解

本來暴力可破，到了115/134個用例時超過了時間限制。本題可用字典樹優化暴力算法。先把各個字元串倒序插入字典樹，可分三種情況。

①字典樹中有目前字元串的翻轉單詞 符合題意

class Solution {
    public class Trie {
        Trie[] next;
        //end表示這目前這棵樹是那一個索引單詞的結尾
        int end;

        public Trie() {
            this.next =  new Trie[26];
            this.end = -1;
        }
        //由于待會兒用到字典樹的時候，是找目标串的翻轉字元串，是以插入的時候，應該是倒序插入
        public void insert(String s, int endNum){
            char[] chars = s.toCharArray();
            Trie cur = this;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if (cur.next[index] == null) cur.next[index] = new Trie();
                cur = cur.next[index];
            }
            cur.end = endNum;
        }
    }
    public List<List<Integer>> palindromePairs(String[] words) {
        //建構字典樹
        Trie trie = new Trie();
        for (int i = 0; i < words.length; i++) {
            trie.insert(reverse(words[i]), i);
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            //先去字典樹中找整個單詞的翻轉作為特殊情況考慮
            int index = findWord(trie, word);
            if (index != -1 && index != i) {
                addRes(res, i, index);
            }
            //還有一種特殊情況，我也是送出了沒有通過才發現的，就是單詞裡有空字元串"",
            //這意味他可以放在任何回文串的首尾
            if (isPalindrome(word)) {
                index = findWord(trie, "");
                if (index != -1 && index != i) addRes(res, i, index);
            }
            for (int j = 0; j < word.length(); j++) {
                String ls = word.substring(0, j + 1);
                String rs = word.substring(j + 1);
                //先判斷前半部分[0, j]是不是回文串
                if (isPalindrome(ls)) {
                    int pre = findWord(trie, rs);
                    if (pre != -1 && pre != i) addRes(res, pre, i);
                }
                //再判斷[j + 1, end],一定要加j != word.length() - 1,要不然會和上面找整個字元串的翻轉重複
                if (j != word.length() - 1 && isPalindrome(rs)) {
                    int after = findWord(trie, ls);
                    if (after != -1 && after != i) addRes(res, i, after);
                }
            }
        }
        return res;
    }

    private void addRes(List<List<Integer>> res, int i, int j) {
        List<Integer> list = new ArrayList<>();
        list.add(i);
        list.add(j);
        res.add(list);
    }

    private boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        char[] letters = s.toCharArray();
        while (i < j) {
            if (letters[i] != letters[j]) return false;
            i++;
            j--;
        }
        return true;
    }

    private int findWord(Trie trie, String word) {
        Trie cur = trie;
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int temp = chars[i] - 'a';
            if (cur.next[temp] == null) return -1;
            else cur = cur.next[temp];
        }
        return cur.end;
    }

    private String reverse(String word) {
        StringBuilder sb = new StringBuilder(word);
        return sb.reverse().toString();
    }

}