# Palindrome Pairs

is taken from leetcode

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:

Input: ["abcd","dcba","lls","s","sssll"]

Output: [[0,1],[1,0],[3,2],[2,4]]

Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]

Output: [[0,1],[1,0]]

Explanation: The palindromes are ["battab","tabbat"]

My solution

/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function(words) {
const index = [];
for(let i = 0; i < words.length; i++) {
for (let j = 0; j < words.length; j++) {
if (i !== j) {
if (isPalindrome(words[i] + words[j])) { index.push([i, j]); }
}
}
}
return index;
};

const isPalindrome = (word) => {
const len = word.length / 2 + 1;
const wordLength = word.length - 1;
for (let i = 0; i < len; i++){
if (word[i] !== word[wordLength - i]) {
return false;
}
}
return true;
};

• isPalindrome can be a one-liner with return word === word.split("").reverse().join("");, which means that you can actually inline the check inside of palindromPairs – ChatterOne May 27 at 10:11
• @ChatterOne: I know, but it's too slow – thadeuszlay May 27 at 12:50

First, at a very high level, let me say that I find the implementation straightforward to read and easy to verify correct.

/**
* @param {string[]} words
* @return {number[][]}
*/


Given the context and the fact that the code is essentially use-and-throw-away, I can understand why you didn't provide more documentation than this for palindromePairs. I'm not sure, though, why there isn't corresponding documentation for isPalindrome, which is almost certainly reusable.

var palindromePairs = function(words) {

const isPalindrome = (word) => {


Why is one var and one const?

      if (i !== j) {
if (isPalindrome(words[i] + words[j])) { index.push([i, j]); }
}


I would prefer a single condition instead of an extra layer of indentation:

      if (i !== j && isPalindrome(words[i] + words[j])) {
index.push([i, j]);
}


  const len = word.length / 2 + 1;
const wordLength = word.length - 1;


I don't find these names helpful - particularly the second one, for which I would prefer something like lastIndex. Alternatively it can be written with two indices as

  for (let i = 0, j = word.length - 1; i < j; i++, j--) {
if (word[i] !== word[j]) {
return false;
}
}


Having said all that: why was this exercise in leetcode? I suspect that the intention was to push you to a more sophisticated algorithm than this one, which is brute force. It might be a valuable exercise for you to see whether you can find a more efficient solution, perhaps using trees of some kind...

• That's true. It's not optimal. But based on my skills right now, it's currently the best I could come up within an hour. Thanks for your input. – thadeuszlay May 27 at 18:15

First of all, your code is readable.Try and use more generic variable names like endIndex instead of wordLengthin isPalindrome as the function can certainly be reused.

I think the purpose of the question was for you to develop an algorithm for the problem, and not just use brute force.Also, this does not seem to me to be a problem that can be solved linearly, so maybe try something with best case linear and worst case O(n^2)