1
\$\begingroup\$

The task

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;
};
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – ChatterOne May 27 at 10:11
  • 1
    \$\begingroup\$ @ChatterOne: I know, but it's too slow \$\endgroup\$ – thadeuszlay May 27 at 12:50
2
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – thadeuszlay May 27 at 18:15
1
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.