单词数组中的回文对

Question

我遇到了回文对问题的代码，使用 Trie。

public static class Trie {
    int pos;
    Trie[] nodes;   // consider xyxabc. if current trie is 'a'. Then a.nodes has information. It means string after a is palindrome
    List<Integer> palins;
    public Trie() {
        pos = -1;
        nodes = new Trie[26];
        palins = new ArrayList<>();
    }
}

public static void add(Trie root, String word, int pos) {
    for (int i = word.length() - 1; i >= 0; i--) {
        char ch = word.charAt(i);
        if (isPalindrome(word, 0, i)) { // check if substring(0, i) is palindrome.
            root.palins.add(pos);
        }
        if (root.nodes[ch - 'a'] == null) {
            root.nodes[ch - 'a'] = new Trie();
        }
        root = root.nodes[ch - 'a'];
    }
    root.pos = pos; // if it is xyxcba. Until now, the node should be at x.
    root.palins.add(pos);
}

public static void search(Trie root, String[] words, int i, List<List<Integer>> ans) {
    int len = words[i].length();
    for (int j = 0; j < len && root != null; j++) {
        if (root.pos >= 0 && i != root.pos && isPalindrome(words[i], j, len - 1)) {
            ans.add(Arrays.asList(new Integer[] {i, root.pos}));
        }
        char ch = words[i].charAt(j);
        root = root.nodes[ch - 'a'];
    }
    if (root != null && root.palins.size() > 0) { // assume 'xyxabc' is in trie, now try 'cba'
        for (int j : root.palins) {
            if (j != i) {
                ans.add(Arrays.asList(new Integer[] {i, j}));
            }
        }
    }
}

public static List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> ans = new ArrayList<>();
    Trie trie = new Trie();
    for (int i = 0; i < words.length; i++) {
        add(trie, words[i], i);
    }
    for (int i = 0; i < words.length; i++) {
        search(trie, words, i, ans);
    }
    return ans;
}

public static boolean isPalindrome(String str, int i, int j) {
    while (i < j) {
        if (str.charAt(i++) != str.charAt(j--)) {
            return false;
        }
    }
    return true;
}

任何人都可以帮助我理解，我们在 add 方法的这一行中试图做什么。

if (isPalindrome(word, 0, i)) { // check if substring(0, i) is palindrome.
            root.palins.add(pos);
        }

为什么我们需要在 FOR 循环之外添加：

root.palins.add(pos);

我从这里看到这段代码： http://www.allenlipeng47.com/blog/index.php/2016/03/15/palindrome-pairs/

但是我仍然觉得很难理解这种方法。

谢谢

Answer 1

我认为您链接到的博客 post 没有很好地解释解决方案的核心思想。这可能是代码难以理解的原因。

让我们从问题开始（因为您没有引用它）：

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"]

words[i]和words[j]两个词什么时候满足words[i] + words[j]条件是回文？

如果 words[i] 和 words[j] 的长度相等，则 words[i] 必须等于 words[j] 的倒数（反之亦然）。
如果其中一个单词（例如，words[i]）较长，则它必须以 words[j] 的反转结尾，而 words[i] 的其余部分必须是回文。
例如，取 lls 和 s。 lls以s结尾，ll是回文。所以s+lls就是回文

注意到这一点后，我们基本上需要一种有效的方法来检查某些 words[i] 是否以 words[j] 的反向结尾以及 words[i] 的其余部分是否为回文。

这是使用 Trie 结构实现的，该结构在反向单词上构建基数树。博客 post 给出了构建 Trie 单词 "cbaaa", "bc", "abc":

的一个很好的例子

这 Trie 使得搜索前缀非常高效。例如，搜索 cba（abc 的反向）会给出从 cbaaa.

开始的节点

我认为理解代码的主要问题是由于命名不当的字段（而且代码通常有点乱）。不清楚 pos 和 palins 是什么，所以这可能会给您带来麻烦。

给定 Trie 节点的

pos 只是由从 "root" 到给定节点的节点序列形成的单词的索引。在上面的示例中，cbaaa 具有索引 0，bc 具有索引 1，abc 具有索引 2。相应的节点具有适当的 pos 值。

palins有点意思。在将 Trie 构建到某个节点时，我们有一些共同的前缀。例如，当 Trie 建立到 c-b-a-a-a 中的节点 a 时，我们有公共前缀 cba。但是我们还需要快速检查的是这个词的其余部分是回文。这就是 palins 的用途。 palins 保存以我们迄今为止在构造中使用的公共前缀开头的单词索引，并且该单词的其余部分是回文。在我们的示例中，cbaaa 以 cba 开头，其余 aa 是回文。因此 words 中 cbaaa 的索引 0 将被添加到 palins。如果有类似 cbatt 的东西，它的索引也会添加到 palins.
我们还需要考虑像 abc - cba 这样没有余数的情况。这是通过将单词的索引添加到最后一个符号的节点的 palins 来完成的（这就是为什么您在 for 循环之外看到另一个 root.palins.add(pos); 的原因）。

现在应该或多或少清楚了搜索方法是如何工作的： * 对于每一个词，搜索前缀，等于把这个词倒过来。如果有这样的前缀，那么Trie中就会有一个对应的节点。 * 如果找到这样的节点，检查palins。这将有效地给出 palindrome-pairs 给定单词的 workds 索引。

例如，当我们搜索 abc 时，我们会在 c-b-a-a-a 中找到第一个 a 节点。前缀 cba 反过来等于 abc。 a 节点的 palins 将包含 0（words 中 cbaaa 的索引），因此我们将 [2, 0] 作为其中之一结果。

单词数组中的回文对

Palindromic pairs in an array of words

java

algorithm

palindrome