Palindrome Pairs

                                            
class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> result;
        unordered_map<string, int> wordIndex;
        
        for (int i = 0; i < words.size(); ++i) {
            wordIndex[words[i]] = i;
        }
        
        for (int i = 0; i < words.size(); ++i) {
            for (int j = 0; j <= words[i].size(); ++j) {
                string left = words[i].substr(0, j);
                string right = words[i].substr(j);
                
                if (isPalindrome(left)) {
                    string rev_right = right;
                    reverse(rev_right.begin(), rev_right.end());
                    if (wordIndex.find(rev_right) != wordIndex.end() && wordIndex[rev_right] != i) {
                        result.push_back({wordIndex[rev_right], i});
                    }
                }
                
                if (!right.empty() && isPalindrome(right)) {
                    string rev_left = left;
                    reverse(rev_left.begin(), rev_left.end());
                    if (wordIndex.find(rev_left) != wordIndex.end()) {
                        result.push_back({i, wordIndex[rev_left]});
                    }
                }
            }
        }
        
        return result;
    }
    
    bool isPalindrome(string& s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            if (s[i] != s[j]) {
                return false;
            }
            ++i;
            --j;
        }
        return true;
    }
};

                                            
class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = 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++) {
            for (int j = 0; j <= words[i].length(); j++) {
                String left = words[i].substring(0, j);
                String right = words[i].substring(j);

                if (isPalindrome(left)) {
                    String reversedRight = new StringBuilder(right).reverse().toString();
                    if (map.containsKey(reversedRight) && map.get(reversedRight) != i) {
                        result.add(Arrays.asList(map.get(reversedRight), i));
                    }
                }

                if (right.length() > 0 && isPalindrome(right)) {
                    String reversedLeft = new StringBuilder(left).reverse().toString();
                    if (map.containsKey(reversedLeft) && map.get(reversedLeft) != i) {
                        result.add(Arrays.asList(i, map.get(reversedLeft)));
                    }
                }
            }
        }
        return result;
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

                                            
bool isPalindrome(char *str, int start, int end) {
    while (start < end) {
        if (str[start++] != str[end--]) {
            return false;
        }
    }
    return true;
}

int** palindromePairs(char **words, int wordsSize, int* returnSize, int** returnColumnSizes) {
    int** result = (int**)malloc(wordsSize * wordsSize * sizeof(int*));
    *returnColumnSizes = (int*)malloc(wordsSize * wordsSize * sizeof(int));
    int count = 0;

    for (int i = 0; i < wordsSize; i++) {
        for (int j = 0; j < wordsSize; j++) {
            if (i != j) {
                char *concat = (char*)malloc(strlen(words[i]) + strlen(words[j]) + 1);
                strcpy(concat, words[i]);
                strcat(concat, words[j]);
                if (isPalindrome(concat, 0, strlen(concat) - 1)) {
                    (*returnColumnSizes)[count] = 2;
                    result[count] = (int*)malloc(2 * sizeof(int));
                    result[count][0] = i;
                    result[count][1] = j;
                    count++;
                }
                free(concat);
            }
        }
    }

    *returnSize = count;
    return result;
}

                                            
function palindromePairs(words: string[]): number[][] {
    const isPalindrome = (str: string): boolean => {
        let left = 0;
        let right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    };

    const result: number[][] = [];

    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words.length; j++) {
            if (i === j) continue;
            if (isPalindrome(words[i] + words[j])) {
                result.push([i, j]);
            }
        }
    }

    return result;
};

To solve this coding challenge, the goal is to determine all pairs of words from the given list that can be concatenated to form a palindrome. Below is the detailed step-by-step explanation of the approach and the pseudocode to achieve the desired solution. The approach used ensures that the solution adheres to the required complexity constraints.

Explanation

The challenge requires us to find pairs of indices \( (i, j) \) such that the concatenation of \( words[i] \) and \( words[j] \) results in a palindrome. Here are the key steps involved in the approach:

Create a Word Index Map :

We utilize a dictionary to map each word to its index in the list. This helps in quick lookups to check the existence of the reversed substrings.

Check All Possible Splits :

For each word in the list, we will examine all possible splits of the word into two substrings. For a word \( "abc" \), the splits considered will be: ("", "abc"), ("a", "bc"), ("ab", "c"), and ("abc", "").
For each split, we check the following:

If the left part of the split is a palindrome and the reverse of the right part exists in the dictionary.
If the right part of the split is a palindrome and the reverse of the left part exists in the dictionary.

Handle Special Cases :

We need to handle the situation where one part is empty. For example, if "" is in the array and we find that any other single non-empty string is a reverse palindrome, the pair \( (i, j) \) or \( (j, i) \) should be included.

Step-by-Step Explanation

Initialize a Dictionary :

We create a dictionary \( wordIndex \) where each key-value pair corresponds to a word and its index in the array.

Iterate Over Words :

For each word, and for each possible split position in the word (including before the first character and after the last character), split the word into two parts: \( left \) and \( right \).

Check Palindromic Properties :

If the \( left \) part is a palindrome, check if the reverse of the \( right \) part exists in our dictionary and forms a valid pair.
If the \( right \) part is a palindrome, check if the reverse of the \( left \) part exists in our dictionary and forms a valid pair.

Store Valid Pairs :

Add the valid pairs to the result list only if they meet the conditions \( i \neq j \).

Below is the detailed pseudocode with comments for clarity:

                                            
// Define a function to find all palindrome pairs
function findPalindromePairs(words):
    // Initialize an empty list for storing the results
    result = []
    
    // Create a dictionary to map each word to its index
    wordIndex = {}
    for i from 0 to length of words - 1:
        wordIndex[words[i]] = i

    // Define a helper function to check if a string is a palindrome
    function isPalindrome(s):
        left = 0
        right = length of s - 1
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    // Iterate over each word in the list
    for i from 0 to length of words - 1:
        word = words[i]
        // Iterate over all possible split positions
        for j from 0 to length of word:
            // Split the word into two parts: left and right
            left = substring of word from start to j
            right = substring of word from j to end
            
            // Check if left part is a palindrome
            if isPalindrome(left):
                // Reverse the right part
                reversedRight = reverse(right)
                // Check if reversedRight is in dictionary and indices are different
                if reversedRight in wordIndex and wordIndex[reversedRight] != i:
                    result.append([wordIndex[reversedRight], i])
                    
            // Check if right part is a palindrome and left part is not empty
            if isPalindrome(right) and length of right > 0:
                // Reverse the left part
                reversedLeft = reverse(left)
                // Check if reversedLeft is in dictionary and indices are different
                if reversedLeft in wordIndex and wordIndex[reversedLeft] != i:
                    result.append([i, wordIndex[reversedLeft]])
    
    // Return the list of palindrome pairs
    return result

In this solution:

We first build a dictionary for quick lookups.
For each word, all possible splits into two substrings are examined.
We then check for palindromic properties and potential pairs using the dictionary for quick retrieval and validation.
This approach ensures that we achieve the desired runtime complexity.