CODEWITHSUNDEEP
javascriptalgorithm
Bob Napkin
Bob Napkin

Reputation: 566

Same strings optimization

Yesterday I had a question about an algorithm to check if two strings are the same. I wrote it:

var isSame = function(a, b) {
  if (a.length !== b.length) return false;

  for (var i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) return false;
  }

  return true;
}

But after, an interviewer asked me to optimize it. I didn't it because I don't understand how I can do it. I forgot to ask interview about the answer because the interviewer left chat so fast. Now, I also can't find on the internet how to do it. That is possible?

Upvotes: 2

Views: 91

Answers (3)

Stefan Woehrer
Stefan Woehrer

Reputation: 690

In practice, you'd obviously just compare that strings. But if you ask yourself how you could improve from an algorithmic point of view, let me say that what you do is the most performant way to compare two strings (at least I think so, I didn't prove it). From an implementation point of view, you could test if loop unrolling helps you speed up the code.

With loop unrolling you basically copy and paste your code in the loop body. This way you have less comparisons (jumps). Use it like this:

var isSame = function(a, b) {
   if (a.length !== b.length) return false;

   var unrollFactor = 5; // This is where you can play around to find better solutions
   var i = 0;

   for (i = 0; i < a.length - unrollFactor; i += unrollFactor) {
      if (a[i] !== b[i]) return false;
      if (a[i+1] !== b[i+1]) return false;
      if (a[i+2] !== b[i+2]) return false;
      if (a[i+3] !== b[i+3]) return false;
      if (a[i+4] !== b[i+4]) return false;
   }

   // If there is a rest, compare it:
   for (i = i-unrollFactor; i < a.length; i++) {
      if (a[i] !== b[i]) return false;
    }

   return true;
}

This is just theoretical. In practice I doubt you'd ever really need this in javascript :)

Upvotes: 0

KooiInc
KooiInc

Reputation: 122898

Well strA === strB should be sufficient for strings.

Or use ES2015's Object.is (which is overkill for strings, I'd say)

Object.is('foo', 'bar') //=> false
Object.is('Bar', 'Bar') //=> true

Upvotes: 0

Carlos
Carlos

Reputation: 6021

Looks pretty canonical to me. You just check for whether the lengths are different and then check each letter.

If there's a hash function, you could just compare the two. But either way it doesn't save you from touching every bit of each string.

Upvotes: 1

Related Questions