Easy to read palindrome checker

Question

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;
  }
}

Answer 1

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)));

Answer 2

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("");
}

Answer 3

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(...));

Answer 4

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.

Answer 5

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.