Palindrome Pairs

The "Palindrome Pairs" problem requires finding all pairs of words in a given list such that concatenating them forms a palindrome. The input is a list of words, and the output is a list of pairs of indices representing the palindrome pairs. The constraint is that we should not use any predefined functions or imports.

Analyze the problem 

To solve the problem, we need to iterate through all possible pairs of words in the list and check if their concatenation forms a palindrome. We'll consider different cases for forming palindromes, such as when one word is the reverse of the other or when one word is the reverse of a suffix or prefix of the other. We'll implement the solution from scratch without using any predefined functions.

Design an algorithm 

To solve the problem, we can use the following algorithm:

1. Create an empty list to store the palindrome pairs.
2. Iterate through all pairs of indices (i, j) in the range of the word list:
   • Concatenate the words at indices i and j.
   • Check if the concatenation forms a palindrome by comparing characters from both ends.
   • If the concatenation is a palindrome, add the pair (i, j) to the list of palindrome pairs.
3. Return the list of palindrome pairs.

Explain your approach 

The approach is to iterate through all possible pairs of words and check if their concatenation forms a palindrome. We'll compare characters from both ends to determine if the concatenation is a palindrome. We'll store the valid pairs in a list and return it as the final result.

Write clean and readable code 

Let's implement the algorithm in Python:

def palindromePairs(words):
    pairs = []

    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            word1 = words[i]
            word2 = words[j]
            concat = word1 + word2

            if isPalindrome(concat):
                pairs.append([i, j])

            concat = word2 + word1

            if isPalindrome(concat):
                pairs.append([j, i])

    return pairs


def isPalindrome(word):
    left = 0
    right = len(word) - 1

    while left < right:
        if word[left] != word[right]:
            return False
        left += 1
        right -= 1

    return True

Test your code 

Let's test the code with an example test case and explain the chosen test case:

# Test case
# Input: ["abcd","dcba","lls","s","sssll"]
# Output: [[0,1],[1,0],[3,2],[2,4]]
words = ["abcd", "dcba", "lls", "s", "sssll"]

pairs = palindromePairs(words)
print(pairs)

This test case is chosen to demonstrate the identification of palindrome pairs ["abcd", "dcba"], ["dcba", "abcd"], ["s", "lls"], and ["lls", "sssll"].

Optimize if necessary 

The given algorithm already iterates through all possible pairs of words, which has a time complexity of O(n^2), where n is the number of words. Further optimization might involve improving the palindrome check by utilizing additional information or reducing unnecessary comparisons. However, within the constraints of not using any predefined functions or imports, there are limitations to optimization.

Handle error cases 

The algorithm assumes that the input is a valid list of words. If an invalid input is provided, such as a non-list or non-string elements, the behavior is undefined. You can add error handling code at the beginning of the palindromePairs function to handle such cases and return an appropriate error message or value.

Discuss complexity analysis 

The time complexity of the algorithm is O(n^2), where n is the number of words in the input list. This is because we iterate through all possible pairs of words. The space complexity is O(1) since we only use a constant amount of additional space to store the pairs.