[LeetCode] 336. Palindrome Pairs

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

Thought process:

Put string -> index into a hash map. Iterate through every string. For each iteration, look at left = substring(0, i) and right = substring(i, string.length).

1. If left is a palindrome, then if there is a string that's the reverse of right, we have a palindrome pair (map.get(reverse(right)), string).
2. Similarly, if right is a palindrome, then if there is a string that's the reverse of left, we have a palindrome pair (string, map.get(reverse(left))).

Solution:

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

public class Solution { public List<List<Integer>> palindromePairs(String[] words) { List<List<Integer>> pairs = new ArrayList<>(); Map<String, Integer> map = new HashMap<>(); for (int i = 0; i < words.length; i++) { map.put(words[i], i); } for (int i = 0; i < words.length; i++) { String word = words[i]; int length = word.length(); for (int j = 0; j <= length; j++) { String left = word.substring(0, j); String right = word.substring(j, length); if (isPalindrome(left)) { String rightReversed = (new StringBuilder(right)).reverse().toString(); int match = map.getOrDefault(rightReversed, i); if (match != i) { List<Integer> pair = new ArrayList<>(); pair.add(match); pair.add(i); pairs.add(pair); } } if (isPalindrome(right)) { String leftReversed = (new StringBuilder(left)).reverse().toString(); int match = map.getOrDefault(leftReversed, i); if (match != i && right.length() > 0) { List<Integer> pair = new ArrayList<>(); pair.add(i); pair.add(match); pairs.add(pair); } } } } return pairs; } private boolean isPalindrome(String word) { int start = 0; int end = word.length() - 1; while (start < end) { if (word.charAt(start) != word.charAt(end)) { return false; } start++; end--; } return true; } }

Time complexity:
The outer for loop takes O(n). The inner for loop runs O(l) times, given the average length of the words is l. isParlindrome runs in O(l). The overall time complexity is O(l^2 n).