LeetCode - Palindrome Pairs
https://leetcode.com/problems/palindrome-pairs/
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.
Solution
Brute force solution
The easiest solution is that for each pair (i, j) we check that if words[i] + words[j] is palin or not. The time complexity is O(N^2*L) where N is the length of words and L is the maximum length of a word.
Better solution
There are two constrains:
1 <= words.length <= 5000
0 <= words[i].length <= 300
So O(N^2*L) is not a good solution. We may need to reduce the time complexity.
When concat newWord = words[i] + words[j] (let assume len(words[i]) > len(words[j])), newWord will only be palindrome when reverse(word[j]) is a prefix of word[i]. The middlePart is the right part of word[i] which is the middle part of newWord. Since newWord is palindrome, the remainPart need to be palindrome. To summarize:
words[i] = leftPart + middlePartwords[j] = rightPartnewWord = leftPart + middlePart + rightPartwhereleftPartandrightParthas equal length.newWordis palindrome only whenleftPart = reverse(rightPart)andmiddlePartis palindrome.
With this idea, for each word, we split into leftPart and middlePart, check if there is reverse(leftPart) in the given words and middlePart is palindrome or not.
Final solution
We can use the above solution to solve the problem. We have to check one more case that we split words[i] = middlePart + rightPart, and check for the reverse(rightPart) existence.
We may have to store a map string -> int where key is the reverse(words[i]) and value is the index i to quickly look up the reverse(part).
There is one edge case, words contains empty string "". You can add this empty string into the begin or end of any palindrome string.
1 | func palindromePairs(words []string) [][]int { |
The time complexity is O(NL^2) and Memory complexity is O(NL+L^2) (O(N) since we have the words N elems with length L, L^2 because the maximum output is L^2 pairs)
Support me via: https://ko-fi.com/iamquang95