The Old techInterview Forum - compare two strings

compare two strings

How to compare two strings using O(n) time with constant space, i.e. no extra variables.

Mark
Friday, March 14, 2003

binary operators

Li-fan Chen
Friday, March 14, 2003

Basically, if bit 1 from stream A and bit 1 from stream B is both 0 or 1... then next.. if end of string then true.. if exit prematurely then false

Li-fan Chen
Friday, March 14, 2003

If I had to do your homework for you.. it
would be like
while not EOF of string
from offset = 0 to offset = 7
if char_from_stream_A.bit(offset) XOR char_from_stream_B.bit(offset) = 0
equality affirmed so far at given offset.. go to next offset or next char of all offsets checke
else
exit abnormally, meaning inequality found somewhere in string
end if

read about XORs

AT http://www.ee.washington.edu/research/denise/www/K12/ES2/Computers/final.pdf

you can also check byte at a time.. same
difference.. check for a binary value of
00000000 out of a byte for XOR output to
affirm equality.
you can do the same while loop.. which just
needs memory space to track where you
are in the string array.

Li-fan Chen
Friday, March 14, 2003

C:
int res = strcmp(szFirst, szSecond);

C++:
bool res = first == second;
int res = strcmp(first.c_str(), second.c_str());

Java:
int res = first.compareTo(second);

Javascript:
var res = first == second;

Perl:
int res = first <=> second;

Python:
res = first == second

Brian
Saturday, March 15, 2003

Thanks guys.
// This is case sensitive comparison
bool MyStrCmp(char *str1, char *str2)
{
    while(*str1 && *str1)
    {
        if(((*str1)^(*str2)) !=0)
            return false;
        else
            *str2++, *str1++;
    }
    return true;
}

Mark
Sunday, March 16, 2003

Two things: I obviously didn't run my code through a compiler/interpreter... the perl is missing '$'s all over the place.

Also, why would anyone write "(((*str1)^(*str2)) !=0" instead of "(*str1!=*str2)"?

Brian
Sunday, March 16, 2003

I might be off a bit here, (I'm actually in the middle of refreshing my C currently) but I think

str2++, str1++;

is a little easier to understand than

*str2++, *str1++;

Meh, I don't know. I can see how *str1++ could be interpreted as "dereference str1, and after that increment str1".

Andy
Monday, March 17, 2003

Also, it's weird since the dereference is not used. If you want, you can move the increment into the test (which *still* should use ==).

Brian
Thursday, March 20, 2003