336 Palindrome Pairs

336. Palindrome Pairs

1. Question

Given a list of unique words, find all pairs of distinct indices(i, j)in the given list, so that the concatenation of the two words, i.e.words[i] + words[j]is a palindrome.

Example 1: Givenwords=["bat", "tab", "cat"] Return[[0, 1], [1, 0]] The palindromes are["battab", "tabbat"] Example 2: Givenwords=["abcd", "dcba", "lls", "s", "sssll"] Return[[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are["dcbaabcd", "abcddcba", "slls", "llssssll"]

2. Implementation

(1) Trie

思路:

(1) 要看两个string连在一起是否回文串，那么这两个string必然满足这样的性质：一个string的前缀和另一个string的后缀相同且除去前(后)缀的剩余是回文串(包括空字符串)。

(2)为了比较不同string的前后缀，我们可以利用trie，插入时将每个word按照倒序放入trie，这样的好处是，当我们查询一个string的前缀时，可以通过trie快速的找到有没与前缀相同的后缀

(3)对于子串中存在回文串的string(包括空字符串), 比如abac中有aba这个回文子串，我们在trieNode里维护一个list，保存这种特性的word在输入数组的index

class Solution {
    class TrieNode {
        //记录word在输入数组的index， 预设值为-1
        int index; 
        // 保存word在输入数组的index，这种word满足条件：
        // word的后缀在trie里, 剩余部分是回文串(包括空串)。比如abac, c为后缀，剩余部分aba。注意abac是倒着插入(即caba)trie的
        List<Integer> list; 
        TrieNode[] childNode;

        public TrieNode() {
            index = -1; 
            list = new ArrayList<>();
            childNode = new TrieNode[26];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        // 将Word倒序的插入Trie里
        public void insert(String word, int index) {
            TrieNode curNode = root;

            for (int i = word.length() - 1; i >= 0; i--) {
                if (isPalindrome(word, 0, i)) {
                    curNode.list.add(index);
                }

                int pos = word.charAt(i) - 'a';

                if (curNode.childNode[pos] == null) {
                    curNode.childNode[pos] = new TrieNode();
                }
                curNode = curNode.childNode[pos];
            }
            curNode.index = index;
            curNode.list.add(index);
        }

        public void search(String word, int index, List<List<Integer>> res) {
            TrieNode curNode = root;

            for (int i = 0; i < word.length(); i++) {
                // curNode.index >= 0 意味着这里有输入数组里的string
                // curNode.index != index 说明curNode.index对应的string和index对应的string不同
                // 当word[i...word.length() - 1]是回文串时，说明curNode.index对应的string和index对应的string可以连在一起形成回文串
                if (curNode.index >= 0 && curNode.index != index && isPalindrome(word, i, word.length() - 1)) {
                    res.add(Arrays.asList(index, curNode.index));
                }

                int pos = word.charAt(i) - 'a';

                if (curNode.childNode[pos] == null) {
                    return;
                }
                curNode = curNode.childNode[pos];
            }

            // 当word在字符串中找到与它相同的string后， 查看curNode.list里的index， 这些index对应的word都是在curNode后面的substring为回文串
            for (int j : curNode.list) {
                if (j != index) {
                    res.add(Arrays.asList(index, j));
                }
            }
        }
    }

    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>();

        if (words == null || words.length == 0) {
            return res;
        }

        Trie trie = new Trie();

        for (int i = 0; i < words.length; i++) {
            trie.insert(words[i], i);
        }

        for (int i = 0; i < words.length; i++) {
            trie.search(words[i], i, res);
        }
        return res;
    }

    public boolean isPalindrome(String word, int start, int end) {
        while (start < end) {
            if (word.charAt(start) != word.charAt(end)) {
                return false;
            }
            ++start;
            --end;
        }
        return true;
    }
}

3. Time & Space Complexity

Trie: 时间复杂度O(nL^2)，n是words里的元素个数，L是words里word的平均长度。空间复杂度O(nL)