Coding Week 10 - Strings

Question 1

Problem 1) Palindrome pairs

You are given a 0-indexed array of unique strings words.
A palindrome pair is a pair of integers (i, j) such that:
0 <= i, j < word.length,
i != j, and
words[i] + words[j] (the concatenation of the two strings) is a palindrome.
Return an array of all the palindrome pairs of words.

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

Question 1) Consider the following approach:

Start by building the Trie. For each word, reverse it and identify its palindrome prefixes (suffixes of the reversed word). Insert the word into the Trie, and mark the final letter as an ending node, and include the word’s index. Also, while inserting, note any points where the remainder of the word is a palindrome suffix by including the index in an additional list (used for case 2).
Then, we go back through the list of words, looking each up in the Trie. Any of the following situations give us palindrome pairs.
We have no letters left on the word and are at a word end node (case 1).
We have no letters left on the word and there are indexes in the list attached to the node (case 2).
We have a palindrome left on the word and are on a word end node (case 3).

What is the time and space complexity of this approach, if implemented properly?
(n be the number of words, and k be the length of the longest word.)

Time - O(k * n), Space - O(k * n)
Time - O(k^2 * n), space - O(k * n)
Time - O(k^2 * n), space - O((k + n)^2)
Time - O(k * n), space - O((k + n)^2)