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

1 Answer 1

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\$
1
  • \$\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\$ May 27, 2019 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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