回文问题（困难题）

2020-08-06

回文对

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。


给定一组 互不相同 的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

示例 1：

输入：["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]] 
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：

输入：["bat","tab","cat"]
输出：[[0,1],[1,0]] 
解释：可拼接成的回文串为 ["battab","tabbat"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

java暴力解法，通过了所有测试点，但是超时了


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.*;
//“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
public class Reword {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<String> slist = new ArrayList<>();
        while (sc.hasNext()) {

            String s = sc.next();
            if (s.equals("1")) {
                break;
            }
            System.out.println(s);

            slist.add(s);

        }

        String[] words = new String[slist.size()];
        for (int i = 0; i < slist.size(); i++) {
            words[i] = slist.get(i);
        }

        List<List<Integer>> result = palindromePairs(words);
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i).get(0) + "\t" + result.get(i).get(1));
        }
    }

    public static List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> outerList = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (isReword(words[i] + words[j])) {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    outerList.add(list);
                }
                if (isReword(words[j] + words[i])) {
                    List<Integer> list = new ArrayList<>();
                    list.add(j);
                    list.add(i);
                    outerList.add(list);
                }

            }
        }
        return outerList;
    }


    public static boolean isReword(String word) {
//        加上注释多通过10多个测试点
//        if (word.length() == 0) {
//            return false;
//        }
//        这样写效率更低
//        if(word.equals(new StringBuffer(word).reverse().toString())){
//            return true;
//        }else{
//            return false;
//        }
//        通过了所有测试点但是还是超时
        int length = word.length() - 1;
        for (int i = 0; i < word.length() / 2; i++) {
            if (word.charAt(i) != word.charAt(length - i)) {
                return false;
            }
        }
        return true;
    }
}

别人的解法：使用字典树和哈希表两种方法

参考文献
LeetCode（336）：回文对 Palindrome Pairs（Java）

//        字典树解法
//
//        从后往前反方向遍历所有单词，构建一棵后缀树（存储翻转的单词）。后缀树的有两个额外成员：
//        reverseWordIdx用于存放翻转单词的单词序号，容器palindPrefixWords存放该结点处除去后缀其余部分能形成回文前缀[0,i]的单词序号。
//        从前往后遍历单词curWord的进行校验。
//
//        如果字典中恰存在一个与curWord[0,j-1]互为翻转的单词reverseWord，且剩余部分curWord[j,end]恰为回文子串，则一定能组合成
//        curWord[0,j-1]+curWord[j,end]+reverseWord[0,end]的回文串。
//
//
//        若遍历结束结点仍不空，说明curWord[0,end]恰与字典中其他单词的部分后缀[j,end]互为翻转。除去翻转后缀后其余部分[0,j-1]能够形成回文的单词palindPrefixWord一定能与curWord构成
//        curWord[0,end]+palindPrefixWord[0,j-1]+palindPrefixWord[j,end]的回文串（j-1=0时为空回文子串，字典中恰有两个单词互为翻转）。


class PalindromePairs {

    //字典树
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = 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++){
            search(words, i, root, result);
        }
        return result;
    }

    private class TrieNode{
        TrieNode[] children;
        int reverseWordIdx;
        List<Integer> palindPrefixWords;
        TrieNode(){
            children = new TrieNode[26];
            reverseWordIdx = -1;
            palindPrefixWords = new ArrayList<>();
        }
    }

    //构建后缀树
    private void addWord(TrieNode root, String word, int curWordIdx){
        //从前往后遍历每一个字符i进行建树
        for(int i = word.length() - 1; i >= 0; i--){
            int loc = word.charAt(i) - 'a';
            if(root.children[loc] == null){
                root.children[loc] = new TrieNode();
            }
            //palindPrefixWords存放在i处除去后缀其余部分能形成回文前缀[0,i]的单词序号
            if(isPalindrome(word, 0, i)){
                root.palindPrefixWords.add(curWordIdx);
            }
            root = root.children[loc];
        }
        //考虑前缀为空串时[0,0]也是回文串，尾结点处palindPrefixWords添加curWordIdx
        root.palindPrefixWords.add(curWordIdx);
        //尾结点的reverseWordIdx存放翻转单词的单词序号
        root.reverseWordIdx = curWordIdx;
    }

    private void search(String[] words, int curWordIdx, TrieNode node, List<List<Integer>> result){
        //从前往后遍历单词curWord的进行校验
        for(int j = 0; j < words[curWordIdx].length(); j++){
            //如果字典中恰存在一个与curWord[0,j-1]互为翻转的单词reverseWord，且剩余部分curWord[j,end]恰为回文子串
            //则一定能组合成curWord[0,j-1]+curWord[j,end]+reverseWord[0,end]的回文串
            if(node.reverseWordIdx >= 0 && isPalindrome(words[curWordIdx], j, words[curWordIdx].length() - 1)){
                result.add(Arrays.asList(curWordIdx, node.reverseWordIdx));
            }
            node = node.children[words[curWordIdx].charAt(j) - 'a'];
            //若后缀路径遇到空值则停止校验并返回
            if(node == null){
                return;
            }
        }
        //若遍历结束结点仍不空，说明curWord[0,end]恰与字典中其他单词的部分后缀[j,end]互为翻转
        //除去翻转后缀后其余部分[0,j-1]能够形成回文的单词palindPrefixWord一定能与curWord构成
        //curWord[0,end]+palindPrefixWord[0,j-1]+palindPrefixWord[j,end]的回文串（j-1=0时为空回文子串，字典中恰有两个单词互为翻转）
        for(int palindPrefixWordIdx : node.palindPrefixWords){
            //排除自身构成回文的重复情况
            if(curWordIdx != palindPrefixWordIdx){
                result.add(Arrays.asList(curWordIdx, palindPrefixWordIdx));
            }
        }
    }

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