代码1

首先把每个单词都放进去这个逆向单词树。然后试着是否能不停的往下走。有两种情况是可以认为当前遍历的词和某个节点可以形成一个结果配对的。如果说我们当前遍历到的单词叫str的话。

当前节点index非空。这就表示str在当前节点上在已经走过了一个完整的单词。此时所需要判断的就是如果str剩下的部分是一个palindrome的话，那么str和该节点对应的index的单词就可以合并成为一个palindrome。当然你需要判断str所在的位置和index不是同一个位置即可。举个例子，如果你有一个word是abc，那么它在树里对应的分支就是c -> b -> a （因为是反向的树），如果str是cbaaba，那么它走到c - > b - > a的时候就会发现abc这个单词已经完结了，然后aba也是一个palindrome, 那么，cbaaba + abc就是cbaabaabc也是一个palindrome。
当前节点的palindromes非空，也就是在这个节点有最少一个单词剩余的substring部分是palindrome。如果此时str已经走完了，就表示这个节点所有的palindromes对应的index都可以和str配对。举个例子，如果有单词dedabc，dabc，edeabc，这样在c->b->a这个branch的a节点上，palindromes链表会有三个index对应前面三个单词。这个时候如果str是"cba"的话，他就会走到这个节点上，然后和前面三个单词凑成palindrome。

Runtime: 26 ms, faster than 92.20% of Java online submissions for Palindrome Pairs.

class Solution {
    class TrieNode {
        TrieNode[] next;
        Integer index;
        List<Integer> list;
        public TrieNode() {
            next = new TrieNode[26];
            index = -1;
            list = new ArrayList();
        }
    }
    public List<List<Integer>> palindromePairs(String[] words) {
        TrieNode root = new TrieNode();
        List<List<Integer>> res = new ArrayList();
        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, res);
        }
        return res;
    }
    public void searchWord
        (TrieNode root, String[] words, int index, List<List<Integer>> res) {
        for (int j = 0; j < words[index].length(); j++) {
            if (root.index >= 0 && root.index != index 
                   && isPalindrome(words[index], j, words[index].length() - 1)) {
                res.add(Arrays.asList(index, root.index));
            }
            root = root.next[words[index].charAt(j) - 'a'];
            if (root == null) return;
        }
        for (int j : root.list) {
            if (j == index) continue;
            res.add(Arrays.asList(index, j));
        }
    }
    public void addWord(TrieNode root, String word, int index) {
        for (int i = word.length() - 1; i >= 0; i--) {
            int j = word.charAt(i) - 'a';
            if (root.next[j] == null) root.next[j] = new TrieNode();
            if (isPalindrome(word, 0, i)) root.list.add(index);
            root = root.next[j];
        }
        root.index= index;
        root.list.add(index);
    }
    public boolean isPalindrome(String word, int i, int j) {
        while (i < j) {
            if (word.charAt(i++) != word.charAt(j--)) return false;
        }
        return true;
    }
}

代码2

public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> ret = new ArrayList<>();
if (words == null || words.length < 2) return ret;
Map<String, Integer> map = new HashMap<String, Integer>();
for (int i=0; i<words.length; i++) map.put(words[i], i);
for (int i=0; i<words.length; i++) {
// System.out.println(words[i]);
for (int j=0; j<=words[i].length(); j++) { // notice it should be "j <= words[i].length()"
String str1 = words[i].substring(0, j);
String str2 = words[i].substring(j);
if (isPalindrome(str1)) {
String str2rvs = new StringBuilder(str2).reverse().toString();
if (map.containsKey(str2rvs) && map.get(str2rvs) != i) {
List<Integer> list = new ArrayList<Integer>();
list.add(map.get(str2rvs));
list.add(i);
ret.add(list);
// System.out.printf("isPal(str1): %s\n", list.toString());
}
}
if (isPalindrome(str2)) {
String str1rvs = new StringBuilder(str1).reverse().toString();
// check "str.length() != 0" to avoid duplicates
if (map.containsKey(str1rvs) && map.get(str1rvs) != i && str2.length()!=0) {
List<Integer> list = new ArrayList<Integer>();
list.add(i);
list.add(map.get(str1rvs));
ret.add(list);
// System.out.printf("isPal(str2): %s\n", list.toString());
}
}
}
}
return ret;
}

private boolean isPalindrome(String str) {
int left = 0;
int right = str.length() - 1;
while (left <= right) {
if (str.charAt(left++) != str.charAt(right--)) return false;
}
return true;
}

336. Palindrome Pairs

336. Palindrome Pairs

代码1

代码2