DEV Community

Discussion on: A coding interview question asked at Google

ferceg profile image

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

bilyachenkooy profile image

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

elisabethgross profile image
elisabethgross Author

Love the stack based approach!

tails128 profile image
Tails128 • Edited on

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.