Are there less memory intensive ways to exclude alphanumeric characters than regular expressions in Javascript?

Question

During an technical interview, I was asked to implement a basic palindrome function that excludes non-alphanumeric characters in Javascript (e.g. "A man, a plan, a canal, Panama."). The code that I came up with essentially looked like this:

function skipNonAlphanumeric(str,i,j) {
  var regex = /[^a-zA-Z0-9]/;
  if(regex.test(str[i])) {
    i++;
    return skipNonAlphanumeric(str,i,j);
  };
  if(regex.test(str[j])) {
    j--;
    return skipNonAlphanumeric(str,i,j);
  };

  return {i: i, j: j};
};

function isPalindrome(str) {
  var j = str.length - 1;
  var i = 0;
  var indices, ci, cj;
  while(i < j) {
    indices = skipNonAlphanumeric(str,i,j);
    i = indices.i;
    j = indices.j;
    ci = str[i].toLowerCase();
    cj = str[j].toLowerCase();

    if(ci !== cj) {
      return false;
    };

    j--;
    i++;
  };
 return true;
};

My interviewer than proceeded to tell me that:

use of regex is overkill and prone to error.

I accepted this statement during the interview, but upon researching it afterwards, I haven't been able to find a good alternative. This answer to a different question suggests that using charCodeAt() is more performant, but I can't imagine that I would be expected to know the necessary character codes to implement a solution like that.

I'm aware that my code isn't necessarily the best solution to the problem, but does anyone have any ideas as to what my interviewer could have been looking for instead?

No, there's nothing wrong with using regex to exclude alphanumeric characters. But there are lots of other things in your code that definitely *are* overkill — Bergi, Sep 06 '17 at 23:49
So you don't actually care about how memory intensive the solution is, contrary to what you asked about in the title? — Bergi, Sep 06 '17 at 23:50
What is a palindrome ? HEre you go, it does or it doesn't `/^[a-zA-Z0-9]*$/` And, you can easily replace `/[^a-zA-Z0-9]+/g` with nothing — , Sep 06 '17 at 23:51
`use of regex is overkill and prone to error` Don't ever work for a shmuck who says this stuff !! — , Sep 06 '17 at 23:55
@sln Well, small expressions like that are quite easy to understand supposing that you have a minimal understanding of RE (which most programmers don't have), but I have seem multi-line monstrosities that require the Rosseta stone to decipher them... — Alberto Martinez, Sep 07 '17 at 00:02
@AlbertoMartinez - Here we go again. Look man, there is no reason to _not_ learn regex. A novice could learn enough in less than a week, to look at advanced regex demo's and get up to speed very quickly. And, there are tools out there that take these 1 liners and format it out into readable code. (http://www.regexformat.com) And do all the manipulation, maintenance and testing you'd ever need. I don't think you've actually seen a regex monster yet = [175,000 word dictionary](http://www.regexformat.com/Dnl/_Samples/_Ternary_Tool%20(Dictionary)/___txt/_ASCII_175,000_word_Mix_A-Z_Multi_Lined.txt) — , Sep 07 '17 at 00:09
Generated with the push of a button. It's all about how to maintain them. Good tools help. — , Sep 07 '17 at 00:10
@sln I'm not again regex, I used to have installed [The Regex Coach](http://www.weitz.de/regex-coach/) and I use regex sporadically (and I could use them more but many times I just forget that I could use them). What I say is that an expression bigger that a couple of lines take a lot of work to understand for people than don't use them everyday (including me), even with the help of tools, so it's more difficult to maintain and debug (obviously that is not your case). — Alberto Martinez, Sep 07 '17 at 00:31
@AlbertoMartinez - Well, I gave you a link. Install the app, drop in the multi-line regex and format it. Take a look at the code. It is just _code_. In the expanded/formatted state it's easy to read, modify, test and convert back into a 1 liner. And, it's not like those verbose and tiresome apps, hovering over things that explain every single syntax. Actually, there is no app that formats it into code, none except this. The reason why is it's waay too complex to do .... Uniquely good. — , Sep 07 '17 at 00:39
@sln, Honestly, I'm bit intrigued, so I'll take a look at that. But I still think that regex are not suited for everyone nor for every task (I have coworkers that I'm sure will suffer a brain meltdown if exposed to a complex regex). — Alberto Martinez, Sep 07 '17 at 00:55
Regex are an indispensable tool, not just for code, but for basic utilities. There are things they shouldn't be used for, but a basic grasp should be in every developer's toolbox. A developer that doesn't know basic regex is almost always a below-average developer. — Dave Newton, Sep 07 '17 at 00:58
I'm not enamored with your solution. That said, if the interviewer thinks regexes are "prone to error" he likely doesn't understand them or something. Find some other place to work. — Michael Chaney, Sep 07 '17 at 01:44

score 2 · Accepted Answer · answered Sep 07 '17 at 00:43

The use of a regular expression is acceptable here, but to use one more than once (character per character) is a waste. If you use one, then use it to remove characters from the string in one go, and perform a regular palindrome test on the result.

Here is an alternative that does that removal without a regular expression, and without knowledge of character codes.

It converts the string to an array, and applies a filter on it, using a Set of allowed characters as the this object:

function isPalindrome(str) {
    str = [...str.toLowerCase()].filter(function (c) {
        return this.has(c);
    }, new Set('abcdefghijklmnopqrstuvwxyz0123456789'));
    for (var i = 0, j = str.length - 1; i < j; i++, j--) {
        if (str[i] !== str[j]) return false;
    }
    return true;
};  

console.log(isPalindrome('A man, a plan, a canal, Panama.'));

I think if you had used `Array.from` instead of spread syntax, and an extra variable `allowedChars` instead of the `this` trick, the code would have been quite self-explanatory — Bergi, Sep 07 '17 at 02:06

Alberto Martinez · Answer 2 · 2017-09-07T01:46:08.630

The old-school method of getting only alphanumeric chars would be using .charAt() and comparing the strings, you don't have to know the character codes. And since you are processing the string char by char you get the reverse string almost for free, so you can know if the string is a palindrome just comparing them:

function isPalindrome(inputStr) {
  var i, char, str="", reverseStr="";
  
  for (i=0;i<inputStr.length;i++) {
    char=inputStr.charAt(i).toLowerCase();
    if ((char>='0' && char<='9') || (char>='a' && char<='z')) {
      str=str+char;
      reverseStr=char+reverseStr;
    }
  }
  console.log(str);
  return (str==reverseStr);
};

console.log(isPalindrome('A man, a plan, a canal, Panama.'));
console.log(isPalindrome('Not really a palindrome'));

If four some reason you want or need to use .charCodeAt(), you just use get the codes for '0'-'9' and 'a'-'z' using also .charCodeAt():

var tempStr='09az';
var code0=tempStr.charCodeAt(0), code9=tempStr.charCodeAt(1),
    codeA=tempStr.charCodeAt(2), codeZ=tempStr.charCodeAt(3);
console.log(code0,code9,codeA,codeZ);

Or `const [code0, code9, codeA, codeZ] = Array.from('09az', c => c.charCodeAt(0));` :-) — Bergi, Sep 07 '17 at 02:08

Are there less memory intensive ways to exclude alphanumeric characters than regular expressions in Javascript?

2 Answers2