336. Palindrome Pairs - jiejackyzhang/leetcode-note GitHub Wiki

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:

Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:

Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

Naive solution是判断每个坐标对是否是回文，时间为O(n^2*k)，n为words个数，k为每个word的平均长度。

efficient solution是采用数据结构Trie来解。

两个字符串相连成为palindrome有如下特征：

  1. s1.length() == s2.length(), s1是s2的reverse。
  2. s1.length() > s2.length(), s1的开始的字符与s2是reverse关系，剩余的字符串是palindrome。
  3. s1.length() < s2.length(), s2的开始的字符与s1是reverse关系，剩余的字符串是palindrome。

对于一个string，将它的字母按从后往前的顺序加入Trie中，如果它的s(0..i)是回文，则将index加入相应TrieNode的list中，string添加完成后，该TrieNode记住它的index。

查找的时候，对于words[i]，

  1. 如果Trie中找到一个完整的string，并且words[i]剩余的字符是回文，则添加至res中；
  2. 如果words[i]的字符遍历完，则最后的那个TrieNode list中的坐标都是满足要求的坐标对。

add和search的过程都是O(k^2)，k为average length of each word，一共有n次iteration，所以总的时间是O(n*k^2)。

public class Solution {
    
    public class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int index = -1;
        List<Integer> list = new ArrayList<>();
    }
    
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>();
        TrieNode root = new TrieNode();
        for(int i = 0; i < words.length; i++) {
            addWord(root, words[i], i);
        }
        for(int i = 0; i < words.length; i++) {
            searchWord(root, words[i], i, res);
        }
        return res;
    }
    
    private void addWord(TrieNode node, String word, int idx) {
        for(int i = word.length()-1; i >= 0; i--) {
            char c = word.charAt(i);
            if(node.children[c-'a'] == null) {
                node.children[c-'a'] = new TrieNode();
            }
            if(isPalindrome(word, 0, i)) node.list.add(idx);
            node = node.children[c-'a'];
        }
        node.list.add(idx);
        node.index = idx;
    }
    
    private void searchWord(TrieNode node, String word, int idx, List<List<Integer>> res) {
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(node.index >= 0 && node.index != idx && isPalindrome(word, i, word.length()-1)) {
                // there is a word which is a reverse of word[0..i-1]
                // and word[i..n-1] is palindrome
                res.add(Arrays.asList(idx, node.index));
            }
            node = node.children[c-'a'];
            if(node == null) return;
        }
        // there are words which is a reverse of word[0..n-1] from the end
        // and the rest is palindrome
        for(int index : node.list) {
            if(index == idx) continue;
            res.add(Arrays.asList(idx, index));
        }
    }
    
    private boolean isPalindrome(String word, int i, int j) {
        while(i < j) {
            if(word.charAt(i) != word.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}
⚠️ **GitHub.com Fallback** ⚠️