Leetcode: 336. Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Code (Java):

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (words == null || words.length == 0) {
            return result;
        }
        
        // step1: put the reverse order of the words into a map
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String rWord = reverse(words[i]);
            map.put(rWord, i);
        }
        
        // step 2 & 3: check the prefix of each word. 
        // It can form a palindrome iff prefix in the map AND 
        // rest substring is a palindrome. 
        // e.g. abll, if the prefix is ab, and the map contains a "ab", then
        // we can form a palindrome which is abllba
        
        // check the postfix of each word. 
        // The word can form a palindrome iff postfix is in the map AND
        // the rest of prefix is a palindrome
        // e.g. llab, where the postfix is ab, if the map cotnains a "ab", then
        // we can form a palindrome of ballab
        for (int j = 0; j < words.length; j++) {
            String word = words[j];
            
            // get prefix of each word
            for (int i = 0; i <= word.length(); i++) {
                String prefix = word.substring(0, i);
                String rest = word.substring(i);
                if (map.containsKey(prefix) && isPalindrome(rest) && 
                    map.get(prefix) != j) {
                    List<Integer> curr = new ArrayList<>();
                    curr.add(j);
                    curr.add(map.get(prefix));
                    result.add(curr);
                }
            }
            
            // get postfix of each word
            for (int i = word.length(); i > 0; i--) {
                String postfix = word.substring(i);
                String rest = word.substring(0, i);
                if (map.containsKey(postfix) && isPalindrome(rest) && 
                    map.get(postfix) != j) {
                    List<Integer> curr = new ArrayList<>();
                    curr.add(map.get(postfix));
                    curr.add(j);
                    result.add(curr);
                }
            }
        }
        
        return result;
    }
    
    private String reverse(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        char[] array = s.toCharArray();
        int start = 0;
        int end = array.length - 1;
        
        while (start < end) {
            swap(start, end, array);
            start++;
            end--;
        }
        
        return new String(array);
    }
    
    private void swap(int start, int end, char[] array) {
        char temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }
    
    private boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        
        int start = 0;
        int end = s.length() - 1;
        
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        
        return true;
    }
}

Analysis:
Assume the number of words is n, and the average length of a word is m. The average time complexity is O(m^2 * n). 
Space complexity: O(n) since we use a map to store all the words