336. Palindrome Pairs – Leetcode Solutions

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"]

Example 2:

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        # Create a dictionary to store the reversed word as the key and its index as the value
        word_map = {word[::-1]: i for i, word in enumerate(words)}
        result = []

        # A helper function to check if a given string is a palindrome
        def is_palindrome(word):
            return word == word[::-1]

        # Iterate through each word and its index
        for i, word in enumerate(words):
            word_len = len(word)

            # Try to split the word into two parts: prefix and suffix
            for j in range(word_len + 1):
                prefix = word[:j]
                suffix = word[j:]

                # If the prefix is a palindrome, check if the reversed suffix exists in the map
                # and make sure that the found word is not the same as the current word
                if is_palindrome(prefix) and suffix in word_map and word_map[suffix] != i:
                    result.append([word_map[suffix], i])

                # If the suffix is a palindrome, check if the reversed prefix exists in the map
                # Ensure that j != word_len to avoid duplicate entries
                if j != word_len and is_palindrome(suffix) and prefix in word_map and word_map[prefix] != i:
                    result.append([i, word_map[prefix]])

        return result

class Solution {
public:
    // Function to check if a string is a palindrome
    bool isPalindrome(const string& str) {
        int left = 0;
        int right = str.length() - 1;
        
        // Compare characters from both ends
        while (left < right) {
            if (str[left] != str[right]) return false;
            ++left;
            --right;
        }
        return true;
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        // Resultant vector to store palindrome pairs
        vector<vector<int>> result;
        
        // Hash map to store reversed words and their indices
        unordered_map<string, int> reversedWords;
        
        // Populate the hash map with reversed words
        for (int i = 0; i < words.size(); ++i) {
            string reversed = words[i];
            reverse(reversed.begin(), reversed.end());
            reversedWords[reversed] = i;
        }

        // Iterate over each word to find palindrome pairs
        for (int i = 0; i < words.size(); ++i) {
            string word = words[i];
            
            // Check all possible splits of the word into two parts
            for (int j = 0; j <= word.length(); ++j) {
                // Split the word into a prefix and a suffix
                string prefix = word.substr(0, j);
                string suffix = word.substr(j);

                // Case 1: If the prefix is a palindrome, check if the reversed suffix exists in the map
                if (isPalindrome(prefix)) {
                    if (reversedWords.count(suffix) && reversedWords[suffix] != i) {
                        result.push_back({reversedWords[suffix], i});
                    }
                }

                // Case 2: If the suffix is a palindrome, check if the reversed prefix exists in the map
                // Note: Skip j == word.length() to avoid duplicate pairs (i, i) 
                if (j != word.length() && isPalindrome(suffix)) {
                    if (reversedWords.count(prefix) && reversedWords[prefix] != i) {
                        result.push_back({i, reversedWords[prefix]});
                    }
                }
            }
        }

        return result;
    }
};

var palindromePairs = function(words) {
    // Result array to store all pairs of palindrome pairs.
    const result = [];
    
    // A map to store the word as the key and its index as the value for fast lookups.
    const wordMap = new Map();
    
    // Helper function to check if a given string is a palindrome.
    const isPalindrome = (str) => {
        let left = 0, right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    };

    // Store each word and its index in the map
    for (let i = 0; i < words.length; i++) {
        wordMap.set(words[i], i);
    }

    // Loop over each word to find potential palindrome pairs
    for (let i = 0; i < words.length; i++) {
        const word = words[i];

        // Split the word into two parts and check each part
        for (let j = 0; j <= word.length; j++) {
            const prefix = word.substring(0, j);  // First part
            const suffix = word.substring(j);     // Second part

            // Case 1: If the prefix is a palindrome, check if there's a reverse of the suffix in the map
            if (isPalindrome(prefix)) {
                const reverseSuffix = suffix.split('').reverse().join('');
                if (wordMap.has(reverseSuffix) && wordMap.get(reverseSuffix) !== i) {
                    result.push([wordMap.get(reverseSuffix), i]);
                }
            }

            // Case 2: If the suffix is a palindrome, check if there's a reverse of the prefix in the map
            // Also, we need to make sure j !== word.length to avoid duplicating the case where the word is split fully.
            if (isPalindrome(suffix) && j !== word.length) {
                const reversePrefix = prefix.split('').reverse().join('');
                if (wordMap.has(reversePrefix) && wordMap.get(reversePrefix) !== i) {
                    result.push([i, wordMap.get(reversePrefix)]);
                }
            }
        }
    }
    
    // Return the list of palindrome pairs.
    return result;
};

class Solution {
    // Function to return a list of all palindrome pairs
    public List<List<Integer>> palindromePairs(String[] words) {
        // Initialize the result list to store palindrome pairs
        List<List<Integer>> result = new ArrayList<>();

        // Edge case: if the input is empty, return an empty result
        if (words == null || words.length < 2) {
            return result;
        }

        // Create a map to store the reversed word and its index in the original array
        Map<String, Integer> reversedWordMap = new HashMap<>();

        // Populate the reversedWordMap with reversed words and their indices
        for (int i = 0; i < words.length; i++) {
            reversedWordMap.put(new StringBuilder(words[i]).reverse().toString(), i);
        }

        // Iterate over each word in the words array
        for (int i = 0; i < words.length; i++) {
            String currentWord = words[i];

            // Check for palindrome pairs by splitting the word into left and right substrings
            for (int j = 0; j <= currentWord.length(); j++) {
                String left = currentWord.substring(0, j); // Left substring
                String right = currentWord.substring(j);   // Right substring

                // Case 1: If left is a palindrome and there's a reversed word matching the right
                if (isPalindrome(left)) {
                    // Check if the reversed right substring exists in the map
                    Integer rightIndex = reversedWordMap.get(right);
                    if (rightIndex != null && rightIndex != i) {
                        result.add(Arrays.asList(rightIndex, i)); // Add to result
                    }
                }

                // Case 2: If right is a palindrome and there's a reversed word matching the left
                // To avoid duplicates, check j != currentWord.length() since we already check for full string palindrome in Case 1
                if (j != currentWord.length() && isPalindrome(right)) {
                    // Check if the reversed left substring exists in the map
                    Integer leftIndex = reversedWordMap.get(left);
                    if (leftIndex != null && leftIndex != i) {
                        result.add(Arrays.asList(i, leftIndex)); // Add to result
                    }
                }
            }
        }

        // Return the list of palindrome pairs
        return result;
    }

    // Helper function to check if a given string is a palindrome
    private boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;

        // Check if the string reads the same forwards and backwards
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false; // Not a palindrome
            }
            left++;
            right--;
        }

        return true; // It is a palindrome
    }
}