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 + middlePart
  • words[j] = rightPart
  • newWord = leftPart + middlePart + rightPart where leftPart and rightPart has equal length.
  • newWord is palindrome only when leftPart = reverse(rightPart) and middlePart is 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
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
62
63
64
65
66
func palindromePairs(words []string) [][]int {
// Build a reverse string map
emptyStrIdx := -1
revMap := make(map[string]int)
for i, word := range words {
revMap[revStr(word)] = i
if word == "" {
emptyStrIdx = i
}
}

// Build result
result := make([][]int, 0)
for i, word := range words {
// For each word, we split into two parts: left and right
// We may build a palin using these two part in 2 ways:
// - left right X, with X is rev(left)
// - X left right, with X is rev(right)
for leftIdx := range word {
leftPart := word[:leftIdx]
rightPart := word[leftIdx:]

if j, ok := revMap[leftPart]; ok {
if j != i && isPalin(rightPart) {
result = append(result, []int{i, j})
}
}

if j, ok := revMap[rightPart]; ok {
if j != i && isPalin(leftPart) {
result = append(result, []int{j, i})
}
}

}
}

// Handle special case when there is an empty string
// In the happy path, we already cover all cases (i, j) where s[j] is empty and s[i] is a palin
// We will miss the case (j, i)
if (emptyStrIdx != -1) {
for i, word := range words {
if i != emptyStrIdx && isPalin(word) {
result = append(result, []int{emptyStrIdx, i})
}
}
}
return result
}

func revStr(s string) string {
rev := make([]rune, len(s))
for i, v := range s {
rev[len(s) - i - 1] = v
}
return string(rev)
}

func isPalin(s string) bool {
for i, j := 0, len(s)-1; i <= j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}

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