11
\$\begingroup\$

I made a palindrome checker that's supposed to be designed to be simple and easy to read. Please let me know what you think. I believe the time complexity is \$\mathcal{O}(n)\$ but I'm not too sure about that:

Challenge: You'll need to remove all non-alphanumeric characters (punctuation, spaces and symbols) and turn everything into the same case (lower or upper case) in order to check for palindromes.

function reverseString(str)
{ 
  str = str.replace(/[^\w\s]|_/g, "").toLowerCase().split(" ").join("");
  var array = [];
  for(var i = str.length ; i >=0; i--)
  {
    array.push(str[i])
  }
  return(array.join(""));
}


reverseString("My age is 0, 0 si ega ym.");

function palindrome(str) {
  str = str.replace(/[^\w\s]|_/g, "").toLowerCase().split(" ").join("");
  if(str === reverseString(str))
  {
   return true; 
  }
  else
  {
    return false;
  }
}
\$\endgroup\$
  • \$\begingroup\$ Are you sure this is working as intended? \$\endgroup\$ – Mast Mar 30 at 18:38
  • \$\begingroup\$ The test reverseString("My age is 0, 0 si ega ym."); should at least be something like console.log(palindrome(reverseString("My age is 0, 0 si ega ym.")));, and does your challenge ignore spaces? Because if they don't, your example string should return false while it doesn't. Please clarify the exact challenge. \$\endgroup\$ – Mast Mar 30 at 18:42
12
\$\begingroup\$

Time complexity

Your time complexity is linear but you can save a few traversals over the string and lower the constant factor as you improve readability. Checking whether a string is a palindrome can be done in one pass with two pointers at each end of the string (plus some conditionals for your special characters), but this gains speed at the expense of readability; I'd encourage a round of clean-up before going for optimizations.

Repeated code

Repeated code harms maintainability and readability. Notice that the line

str.replace(/[^\w\s]|_/g, "").toLowerCase().split(" ").join("");

appears in two places in the code. If you decide to change one to accept a different regex but forget to change the other one, you've introduced a potentially subtle bug into your program. Move this to its own function to avoid duplication.

Use accurate function names and use builtins

reverseString is a confusing function: it does more than reversing a string as advertised: it also strips whitespace and punctuation, which would be very surprising if I called this function as a user of your library without knowing its internals. All functions should operate as black boxes that perform the task they claim to, nothing more or less.

The array prototype already has a reverse() function, so there's no need to write this out by hand.

Avoid unnecessary verbosity

The code:

  if(str === reverseString(str))
  {
   return true; 
  }
  else
  {
    return false;
  }

is clearer written as return str === reverseString(str);, which says "return the logical result of comparing str and its reversal".

Improve the regex to match your specification

Including spaces in your regex substitution to "" is easier than .split(" ").join(""). If you wish to remove all non-alphanumeric characters, a regex like /[^a-z\d]/gi reflects your written specification accurately (or use \W if you don't mind including underscores).

Style remarks

  • JS uses K&R braces instead of Allman by convention.
  • Add a blank line above for and if blocks to ease vertical congestion.
  • Add a space around keywords and operators like for( and >=0, which are clearer as for ( and >= 0.
  • No need for parentheses around a return value.
  • array.push(str[i]) is missing a semicolon.
  • CodeReview's snippet autoformatter will automatically do most of this for you.

Rewrite 1

const palindrome = str => {
  str = str.replace(/[^a-z\d]/gi, "").toLowerCase();
  return str === str.split("").reverse().join("");
};

console.log(palindrome("My age is 0, 0 si ega ym."));

Rewrite 2: uglier, but faster

Benchmark

const palindrome = str => {
  str = str.replace(/[^a-z\d]/gi, "").toLowerCase();
  let left = 0;
  let right = str.length;

  while (left < right) {
    if (str[left++] !== str[--right]) {
      return false;
    }
  }

  return true;
};

[
  "",
  "a",
  "aba",
  "racecar",
  "racecar ",
  " racecar",
  " race car",
  " r  r a c e   c a  rr     ",
  ".a .. r . ... . .{9f08e988-1e35-4dc6-a24a-5c7e03bce5ba}$ $!ace ca r3  a",
].forEach(test => console.log(palindrome(test)));

console.log();
[
  "ab",
  "abc",
  "racecars",
  "racescar",
  " ra scecar",
  " r   sace car",
  "a r  r a c e   c a  rr     ",
  " r  r a c e   c a  rr     a",
  ".a .. r . ... . .$$$ $!aces ca r  a",
].forEach(test => console.log(palindrome(test)));

\$\endgroup\$
  • \$\begingroup\$ Good points, just to make sure is the time complexity O(n) because the reverse function traverses through each element of the array? \$\endgroup\$ – DreamVision2017 Mar 30 at 21:20
  • \$\begingroup\$ Your code makes ~11 trips over the n-sized input, which is why I mention the high constant factor. If you do the replacement and lowercasing one time, you can get away with about 6 trips through the input. I count any array function, loop or === as one trip over the input. This is a pretty minor concern relative to the other points, though, and addressing the style points accidentally improves your performance along the way. \$\endgroup\$ – ggorlen Mar 30 at 21:30
  • 1
    \$\begingroup\$ Small optimization for your rewrite, lowercase the string first and avoid the additional cost of a case-insensitive regex. There are larger optimizations that could also be done, but that make the code more complicated. \$\endgroup\$ – cbojar Mar 31 at 0:06
  • 1
    \$\begingroup\$ @Feathercrown ==/=== doesn't work on arrays, unfortunately, but good thought. \$\endgroup\$ – ggorlen Mar 31 at 0:17
  • 2
    \$\begingroup\$ Of course, the goal is to get an "easy to read" palindrome checker. Frankly, I doubt that the improvements to the efficiency of the method, impressive though they are, outweigh the looming disaster that would be maintaining or reading them. \$\endgroup\$ – Feathercrown Mar 31 at 5:14
4
\$\begingroup\$

Too much code.

  • You can return a boolean

Note that the positions of { and }

 if(str === reverseString(str)) {
   return true; 
  } else {
    return false;
  }

Becomes

 return str === reverseString(str);
  • You can remove whites spaces and commas etc with regExp /\W/g

  • Array has a reverse function which you can use rather than do it manually.

  • You should reverse the string in the function.

  • Strings are iterate-able so you can convert a string to an array with [...str]

Example

function isPalindrome(str) {
    str = str.replace(/\W/g,"").toLowerCase();
    return str === [...str].reverse().join("");
}
\$\endgroup\$
  • \$\begingroup\$ Ah I see, btw I tried to code from scratch as much as possible to get better at problem solving/ programming. Although you are right that there are many JS methods that would make it easier to implement a solution. \$\endgroup\$ – DreamVision2017 Mar 30 at 21:31
1
\$\begingroup\$

The line to scrub punctuation and spaces could be simplified from:

str = str.replace(/[^\w\s]|_/g, "").toLowerCase().split(" ").join("");

to:

str = str.replace(/[^\w]|_/g, "").toLowerCase();

Essentially, your original regex marks spaces as legal characters, which you're then going and later scrubbing out with .split(" ").join(""). By excluding the \s in your regex, you cause the regex to match spaces in the string, which would then be replaced along with the punctuation in the str.replace method. See this regex101.

I'd also ask you to consider what it means to be a palindrome. Words like racecar. The way you're currently doing it is by reversing the string, and then checking equality. I suggest it could be half (worst case) or O(1) (best case) the complexity if you'd think about how you could check the front and the back of the string at the same time. I won't give you the code how to do this, but I'll outline the algorithm. Consider the word Urithiru, a faster way to check palindrome-ness would to be doing something like this: Take the first and last letters, compare them, if true, then grab the next in sequence (next from the start; next from reverse). Essentially the program would evaluate it in these steps:

  1. u == u: true
  2. r == r: true
  3. i == i: true
  4. t == h: false

Words like Urithiru and palindromes have the worst complexity cases for the algorithm because every letter must be checked to prove it's a palidrome. However, if you checked a work like supercalifragilisticexpialidocious, it'd only take two iterations, and then most words in the English language (the ones that don't start and end with the same letters), would be an O(1) result. For instance, English would fail after the first comparison.

\$\endgroup\$
1
\$\begingroup\$

I would suggest separating out the code to remove punctuation and convert to lowercase into a separate function (normalizeString), and make the reverseString and isPalindrome functions "purer". (This follows the Single Responsibility Principle.)

function reverseString(str) {
    var array = [];

    for(var i = str.length - 1; i >= 0; --i) {
        array.push(str[i]);
    }

    return(array.join(""));
}

function isPalindrome(str) {
    let left = 0;
    let right = str.length;

    while (left < right) {
        if (str[left++] !== str[--right]) {
            return false;
        }
    }

    return true;
};

function normalizeString(str) {
    return str.replace(/[^\w\s]|_/g, "").toLowerCase().split(" ").join("");
}

// reverseString(normalizeString(...));
// isPalindrome(normalizeString(...));
\$\endgroup\$
  • \$\begingroup\$ Ok, but I'm a little confused on why you used the while loop on your palindrome function, when you can use the reverseString or array.reverse() to compare both strings? It's actually why I created that function. \$\endgroup\$ – DreamVision2017 Mar 31 at 17:30
  • \$\begingroup\$ @DreamVision2017 For efficiency: this isPalindrome implementation can stop as soon as it finds a pair of characters that don't match. \$\endgroup\$ – Solomon Ucko Mar 31 at 17:31
0
\$\begingroup\$

The main contribution of this answer is to use toLowerCase() before the regex, so the regex does less work. Note that I don't know if that would benefit performance at all - profile it if you are curious.

// private implementation - separated for ease of testing
const _isPalindrome = x => x===[...x].reverse().join('');
const _alphanum = x => x.toLowerCase().replace(/[^a-z\s]/g, '');

// public interface - combined for ease of use
const isPalindrome = x => _isPalindrome(_alphanum(x));

This may be unpopular, but I prefer terse/abstract argument names x and y over longer, more specific names. It's similar to using i as a loop variable - it makes it easier to see the structure of the code.

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