Problem

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”]`

The key point of this problem is to find whether each word in the given array has a substring which is a palindrome. If so, check other words one by one to see if the concatenation can be a palindrome; or find out a revserse word of the current one.

Therefore, we need to implement Manacher’s algorithm of Longest Palindromic Substring

Also, we can use Trie structure, but…, anyway it’s a good chance to learn this advanced structure right now.

However, I only come up with a brute force solution, which checks every pairs of words to see if the concatenation is a palindrome.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i != j && isPalindrome(words[i], words[j])) {
                    List<Integer> item = new ArrayList<Integer>();
                    item.add(i);
                    item.add(j);
                    result.add(item);
                }
            }
        }
        return result;
    }
    public boolean isPalindrome(String word1, String word2) {
        int i = 0;
        int j = word2.length() - 1;
        while (i < word1.length() && j >= 0) {
            if (word1.charAt(i) != word2.charAt(j)) {
                return false;
            }
            i += 1;
            j -= 1;
        }
        if (word1.length() < word2.length()) {
            i = 0;
            while (i < j) {
                if (word2.charAt(i) != word2.charAt(j)) {
                    return false;
                }
                i += 1;
                j -= 1;
            }
        } else if (word1.length() > word2.length()) {
            j = word1.length() - 1;
            while (i < j) {
                if (word1.charAt(i) != word1.charAt(j)) {
                    return false;
                }
                i += 1;
                j -= 1;
            }
        }
        return true;
    }
}

I know it’s a naive solution.

Emporia Road