Palindrome Pairs

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.

Example 1:

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

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PalindromePairs {
    public static void main(String[] args) {
        String words[] = { "abcd", "dcba", "lls", "s", "sssll" };
        List<List<Integer>> pair = palindromePairs(words);
        System.out.println(Arrays.asList(pair));
    }
    static boolean isPalindrome(String a, String b) {
        int low = 0, high = b.length() - 1;
        // check for palindrome in string
        // a+b
        while (low < a.length() && high >= 0) {
            if (a.charAt(low) != b.charAt(high))
                return false;
            low++;
            high--;
        }
        if (low == a.length() && high >= 0) {
            low = 0;
            while (low < high) {
                if (b.charAt(low) != b.charAt(high))
                    return false;
                low++;
                high--;
            }
        }
        if (low < a.length() && high < 0) {
            high = a.length() - 1;
            while (low < high) {
                if (a.charAt(low) != a.charAt(high))
                    return false;
                low++;
                high--;
            }
        }
        return true;
    }
//function to find all the palindrome pairs
    static List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (isPalindrome(words[i], words[j])) {
                    List<Integer> l = new ArrayList<Integer>();
                    l.add(i);
                    l.add(j);
                    res.add(l);
                }
                if (isPalindrome(words[j], words[i])) {
                    List<Integer> l = new ArrayList<Integer>();
                    l.add(j);
                    l.add(i);
                    res.add(l);
                }
            }
        }
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(string &a,string &b)
{
        
        int low=0,high=b.size()-1;
        //check for palindrome in string
        // a+b
        while(low<a.size()&&high>=0)
        {
            if(a[low]!=b[high])
                  return false;
            low++;
            high--;
        }
        if(low==a.size()&&high>=0)
        {
            low=0;
            while(low<high)
            {
                if(b[low]!=b[high])
                      return false;
                low++;
                high--;
            }
            
        }
        if(low<a.size()&&high<0)
        {
            high=a.size()-1;
            while(low<high)
            {
                if(a[low]!=a[high])
                      return false;
                low++;
                high--;
            }
        }
        return true;
}
//function to find all the palindrome pairs
vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        for(int i=0;i<words.size()-1;i++)
        {
            for(int j=i+1;j<words.size();j++)
            {
                if(isPalindrome(words[i],words[j]))
                      res.push_back({i,j});
                if(isPalindrome(words[j],words[i]))
                        res.push_back({j,i});
            }
        }
        return res;
}
int main()
{
   vector<string> words={"abcd","dcba","lls","s","sssll"};
   vector<vector<int> > pair=palindromePairs(words);
   cout<<"[";
   for(int i=0;i<pair.size();i++)
      {
          cout<<"[";
          cout<<pair[i][0]<<","<<pair[i][1]<<" ";
           if(i!=pair.size()-1)
              cout<<"],";
        else
          cout<<"]";
      }
      cout<<"]";
   return 0;
}