[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;
    }
}