Same strings optimization

Question

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?

Is this JavaScript? Please add a language tag. Also what's wrong with `return a === b`? — Tagir Valeev, Feb 29 '16 at 10:17
Take a look at [this](http://stackoverflow.com/a/15303672/3541845). A similar question was answered before. — haihui, Feb 29 '16 at 10:17
@TagirValeev: clearly by using library builtins, you do not show much inslight into algorithms — Willem Van Onsem, Feb 29 '16 at 10:18
Optimize in what sense? For performance? Readability? Maintenance? — Codor, Feb 29 '16 at 10:18
@WillemVanOnsem, then the question should specify explicitly what is allowed to use. Why `.length` and `[i]` can be used? Is something else can be used as well? — Tagir Valeev, Feb 29 '16 at 10:18
If you want to optimize to make it not blow up, first check `a` and `b` are not null or undefined — Jamiec, Feb 29 '16 at 10:21
@BobNapkin: an optimization I can think of is reference equality since in most languages string constructs use some kind of flyweight pattern. But I don't know the details how to check reference equality of strings in JavaScript. — Willem Van Onsem, Feb 29 '16 at 10:22
I think @Codor has asked the million dollar question there! If it's for performance, just Google the strcmp algorhythm. If it's for maintenance, put some comments and better variable names in there! — Ben Hillier, Feb 29 '16 at 10:22
@h2ooooooo yep. `function isSame(a,b){ return a===b;}` <- super optimized — Jamiec, Feb 29 '16 at 10:24
@BobNapkin Complexity-wise, without any additional assumptions, it cannot be done faster than `O(n)` where `n` is the sum of the lengths of both strings, as the result depends on each bit of the input. — Codor, Feb 29 '16 at 10:27

score 1 · Answer 1 · answered Feb 29 '16 at 10:18

1

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.

answered Feb 29 '16 at 10:18

Carlos

5,991
6
43
82

2

Actionally you do not need to touch every bit of each string, and OP does not do it either. As soon as you find a difference, you can stop and do not have to check the rest of the strings. – Ridcully Feb 29 '16 at 10:26
2

In the worst case, you will find the strings differ on only the last bit. – Carlos Feb 29 '16 at 10:28
@Ridcully: but that's the case here because of the `return false` in the `if` statement. – Willem Van Onsem Feb 29 '16 at 10:29
@WillemVanOnsem Exactly. As I said, the OP does **not** touch every bit of each string. – Ridcully Feb 29 '16 at 10:41

score 0 · Answer 2 · answered Feb 29 '16 at 10:41

0

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

answered Feb 29 '16 at 10:41

KooiInc

119,216
31
141
177

Does this also work for that? `var a = 'Bar'; var b = 'Bar'; var equal = Object.is(a, b);` ? – Ridcully Feb 29 '16 at 10:43
Sure, it does, just try it in your browser developer console. – KooiInc Feb 29 '16 at 10:45

score 0 · Answer 3 · answered Feb 29 '16 at 13:59

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

Same strings optimization

3 Answers3