[leetCode]336. 回文對

題目

https://leetcode-cn.com/problems/palindrome-pairs/

字首樹

兩個字元串 s1、s2 要構成回文串可以分成三種情況讨論：

• 情況1： s1.length = s2.length

  在這種情況下s1翻轉之後就是s2

• 情況2：s1.length < s2.length, 例如 ：s1 = “as”, s2 = “llsa” \ “sall”

  這種情況 s2能被分成 t1 + t2，其中t1是回文串， t2 是s1的翻轉，也有可能t2是回文串，t1 是s1的翻轉

• 情況3：s1.length > s2.length

  這種情況根第二種情況差不多，s1能被分為兩部分，一部分是回文串另一部分是s2的翻轉

  綜合以上三種情況可以知道，周遊每個字元串将其拆分成兩部分，有一部分是回文串，那麼另一部分就是我們需要查找的對象。我們可以使用字典樹将所有字元串存入，然後逆序查找拆分後回文串的另一部分是否在字典樹中。

class Solution {
    private TrieNode root; 
    
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ans = new ArrayList<>();
        root = new TrieNode();
        for (int i = 0; i < words.length; i++) {
            insert(words[i], i);
        }
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int len =  word.length();
            for (int j = 0; j <= len; j++) { // [0 - j)
                if (isPalidrome(word, j, len - 1)) { // [j , len - 1]
                    Integer idx = findWordIdx(word, 0, j - 1);
                    if (idx != null && idx != i)
                        ans.add(Arrays.asList(i, idx));  
                }
                if (j != 0 && isPalidrome(word, 0, j - 1)) {
                    Integer idx = findWordIdx(word, j, len - 1);
                    if (idx != null && idx != i)  
                        ans.add(Arrays.asList(idx, i));
                }
            }
        }
        return ans;
    }

    class TrieNode {
        Integer index = null;
        TrieNode[] children = new TrieNode[26];
    }

    void insert(String word, int idx) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            cur = cur.children[c - 'a'];
        }
        cur.index = idx;
    }

    Integer findWordIdx(String word, int lo, int hi) {
        TrieNode cur = root;
        for (int i = hi; i >= lo; i--) {
            char c = word.charAt(i);
            if (cur.children[c - 'a'] == null) {
                return null;
            }
            cur = cur.children[c - 'a'];
        }
        return cur.index;
    }

    boolean isPalidrome(String word, int left, int right) {
        while (left < right) {
            if (word.charAt(left) != word.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }
}