DEV Community

loading...

Discussion on: A coding interview question asked at Google

Collapse
ferceg profile image
ferceg

I can't think of anything else other than a stack-based solution.

Collapse
bilyachenkooy profile image
Olexiy

You can try to go in backward direction whule comparing char by char without strings creation. In best case you will determine that strings are different at first iteration. At worst - iterate for max(n, m) times. And in any case you will only need constant extra memory allocation

Collapse
elisabethgross profile image
elisabethgross Author

Love the stack based approach!

Collapse
tails128 profile image
Tails128

I think a stack-based solution is the most efficient and readable method, to be fair...

If we think about the complexity it should be around O(n)
(n (to compute first) + n (to compute second) + n(to go once over both))
Which is ofc not as good as the O(log(n)), but I am not sure there's a way to cut times.

Also we can do a sneaky trick such as

if(stack1.length !== stack2.length) {
  return false;
}

But... to be 100% correct, in order to determine if this is helpful or just added time for our average case we would need to know the context a bit more in depth.