1. Description

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.

2. Runtime Distribution

3. Submission Details

4. Example

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

5. Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.junit.Test;

public class LeetCode0336 {

    private static class Trie{
        int index;
        List<Integer> list;
        Trie[] next;

        public Trie(){
            index = -1;
            list = new ArrayList<Integer>();
            next = new Trie[26];
        }
    }

    public List<List<Integer>> palindromePairs(String[] words) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        Trie root = new Trie();

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

        for(int i = 0; i< words.length; i++){
            trieSearch(root, words, i, res);
        }
        return res;
    }

    private void trieAdd(Trie node, String word, int index){

        for(int i = word.length() - 1; i>=0; i --){
            int pos = word.charAt(i)- 'a';

            if(node.next[pos] == null){
                node.next[pos] = new Trie();
            }

            if(isPalindrome(word, 0, i)){
                node.list.add(index);
            }
            node = node.next[pos];
        }

        node.index = index;
        node.list.add(index);
    }

    private void trieSearch(Trie node, String[] words, int i, List<List<Integer>> res){

        for(int j = 0; j< words[i].length(); j++){

            if(node.index >= 0 && i != node.index && isPalindrome(words[i], j, words[i].length() -1)){
                res.add(Arrays.asList(i, node.index));
            }
            node = node.next[words[i].charAt(j) - 'a'];
            if(node == null){
                return;
            }
        }

        for(int j : node.list){
            if(i != j){
                res.add(Arrays.asList(i, j));
            }
        }
    }

    private boolean isPalindrome(String word, int start,int end){
        while(start <= end && word.charAt(start) == word.charAt(end)){
            start ++;
            end --;
        }
        return start > end;
    }

    @Test
    public void test(){
        String[] words = {
                "a", "abc", "ab"
        };
        System.out.println(palindromePairs(words));
    }
}