Problem

Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

Examples

Example 1:

1
2
3

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

1
2
3

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

Example 3:

1
2

Input: words = ["a",""]
Output: [[0,1],[1,0]]

Solution

Method 1 - Brute Force

There exists an O(n^2 * k) naive approach for this problem, where n is the total number of words in the words array, and k is the average word length. For each word, we iterate through the words array and check if the concatenation results in a palindrome.

This approach causes a Time Limit Exceeded (TLE) error.

Method 2 - Smarter Brute Force

  1. Perform a nested loop on the words array to evaluate pairs of words for palindrome pairs.
  2. Note we dont have to concatenate the strings to check it, we can be smart about it. Rather than concatenating the strings to check for palindromes, the method isPalindrome checks the characters directly from both strings. This approach avoids the overhead of creating new strings.

On 17 Sept, 2022 - Gives TLE.

Code

 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

public List<List<Integer>> palindromePairs(String[] words) {
	int n = words.length;
	List<List<Integer>> result = new ArrayList<>();
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (isPalindrome(words[i], words[j])) {
				result.add(Arrays.asList(i, j));
			}
			if (isPalindrome(words[j], words[i])) {
				result.add(Arrays.asList(j, i));
			}
		}
	}
	return result;
}

private boolean isPalindrome(String word1, String word2) {
	int start = 0;
	int l1 = word1.length();
	int l2 = word2.length();
	int end = l1 + l2 - 1;

	while (start < end) {
		char ch1 = start < l1 ? word1.charAt(start) : word2.charAt(start - l1);
		char ch2 = end >= l1 ? word2.charAt(end - l1) : word1.charAt(end);
		if (ch1 != ch2) {
			return false;
		}
		start++;
		end--;
	}
	return true;
}
 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

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_palindrome(word1: str, word2: str) -> bool:
            start: int = 0
            l1: int = len(word1)
            l2: int = len(word2)
            end: int = l1 + l2 - 1
            
            while start < end:
                ch1: str = word1[start] if start < l1 else word2[start - l1]
                ch2: str = word2[end - l1] if end >= l1 else word1[end]
                if ch1 != ch2:
                    return False
                start += 1
                end -= 1
            return True

        n: int = len(words)
        result: List[List[int]] = []
        for i in range(n):
            for j in range(i + 1, n):
                if is_palindrome(words[i], words[j]):
                    result.append([i, j])
                if is_palindrome(words[j], words[i]):
                    result.append([j, i])
        return result

Complexity

  • ⏰ Time complexity: O(n^2 * m), where n is the number of words and m is the maximum length of any word.
  • 🧺 Space complexity: O(1)

Method 3 - Trie

Here is the approach:

  1. Building the Trie:
    • Construct a Trie where each node represents a character of the words.
    • Store the index of the words at the end of the Trie nodes.
  2. Checking Palindrome Pairs:
    • For each word, check if any concatenation with another word in the Trie forms a palindrome.
  3. Palindrome Checks:
    • Implement helper functions to check if substrings are palindromes.

The Trie node contains:

  • Children nodes.
  • Index of the words completing at that node (for whole words).
  • List of words that can form a palindrome with the current prefix.

Code

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61

public class Solution {
    static class TrieNode {
        TrieNode[] children;
        List<Integer> palindromes;
        int index;

        TrieNode() {
            children = new TrieNode[26];
            palindromes = new ArrayList<>();
            index = -1;
        }
    }

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

    private void addWord(TrieNode root, String word, int index) {
        for (int i = word.length() - 1; i >= 0; i--) {
            if (isPalindrome(word, 0, i)) {
                root.palindromes.add(index);
            }
            int c = word.charAt(i) - 'a';
            if (root.children[c] == null) {
                root.children[c] = new TrieNode();
            }
            root = root.children[c];
        }
        root.palindromes.add(index);
        root.index = index;
    }

    private void searchWords(String[] words, int i, TrieNode root, List<List<Integer>> ans) {
        for (int j = 0; j < words[i].length(); j++) {
            if (root.index >= 0 && root.index != i && isPalindrome(words[i], j, words[i].length() - 1)) {
                ans.add(List.of(i, root.index));
            }
            root = root.children[words[i].charAt(j) - 'a'];
            if (root == null) return;
        }
        
        for (int j : root.palindromes) {
            if (i != j) ans.add(List.of(i, j));
        }
    }

    public List<List<Integer>> palindromePairs(String[] words) {
        TrieNode root = new TrieNode();
        for (int i = 0; i < words.length; i++) {
            addWord(root, words[i], i);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            searchWords(words, i, root, ans);
        }
        return ans;
    }
}
 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

class TrieNode:
    def __init__(self):
        self.children = {}
        self.index = -1
        self.palindromes = []

class Solution:
    def is_palindrome(self, word: str, left: int, right: int) -> bool:
        while left < right:
            if word[left] != word[right]:
                return False
            left += 1
            right -= 1
        return True

    def add_word(self, root: TrieNode, word: str, index: int) -> None:
        for i in range(len(word) - 1, -1, -1):
            if self.is_palindrome(word, 0, i):
                root.palindromes.append(index)
            if word[i] not in root.children:
                root.children[word[i]] = TrieNode()
            root = root.children[word[i]]
        root.palindromes.append(index)
        root.index = index

    def search_words(self, words: List[str], i: int, root: TrieNode, ans: List[List[int]]) -> None:
        for j in range(len(words[i])):
            if root.index >= 0 and root.index != i and self.is_palindrome(words[i], j, len(words[i]) - 1):
                ans.append([i, root.index])
            if words[i][j] not in root.children:
                return
            root = root.children[words[i][j]]
        
        for j in root.palindromes:
            if i != j:
                ans.append([i, j])

    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        root = TrieNode()
        for i, word in enumerate(words):
            self.add_word(root, word, i)
        ans: List[List[int]] = []
        for i in range(len(words)):
            self.search_words(words, i, root, ans)
        return ans

Complexity

  • ⏰ Time complexity: O(n * m^2) where n is the number of words and m is the average length of the words.
  • 🧺 Space complexity: O(n * m) for storing the words in the Trie.