Palindrome Pairs

This page explains Java solution to problem Palindrome Pairs using String data structure.

Problem Statement

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

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

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

Solution

package com.vc.hard;

import java.util.*;

class PalindromePairs {
    public List<List<Integer>> palindromePairs(String[] words) {
        HashMap<String, Integer> wordIndex = new HashMap<>();
        for(int i = 0; i < words.length; i++) wordIndex.put(words[i], i);
        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0; i < words.length; i++) {
            String word = words[i];
            for(int j = 0; j <= word.length(); j++) {
                String w1 = word.substring(0, j);
                String w2 = word.substring(j);

                if(isPalindrome(w1)) {
                    String w2Reverse = reverse(w2);
                    if(wordIndex.containsKey(w2Reverse)) {
                        int k = wordIndex.get(w2Reverse);
                        if(i != k) res.add(Arrays.asList(k, i));
                    }
                }

                if(isPalindrome(w2) && w2.length() != 0) {
                    String w1Reverse = reverse(w1);
                    if(wordIndex.containsKey(w1Reverse)) {
                        int k = wordIndex.get(w1Reverse);
                        if(i != k) res.add(Arrays.asList(i, k));
                    }
                }
            }
        }
        return res;
    }

    private String reverse(String str) {
        int i = 0;
        int j = str.length() - 1;
        char[] cArr = str.toCharArray();
        while(i < j) {
            char temp = cArr[i];
            cArr[i] = cArr[j];
            cArr[j] = temp;
            i++;
            j--;
        }
        return new String(cArr);
    }

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

Time Complexity

O(N * K²) Where
N is total number of elements in an input array
K is length of longest word in a word input array

Space Complexity

O(N) Where
N is total number of elements in an input array