Sign in to follow this  
OleKaiwalker

Searching a string

Recommended Posts

Hey, Given a string only consisting of a's and b's perhaps, which way to determind whether the string contains a equal amount og a's and b's is the fastet? I know that iterating through the whole string counting both entries on the way is a possibility, but it just seems so stupid to me. Anyone's up for a go?

Share this post


Link to post
Share on other sites
Set a signed integer variable to 0. Iterate over the string and for each character if the character is 'a' increment the variable, if it's 'b' decrement the variable.

If the variable is 0 at the end of the loop there are an equal number of 'a' and 'b' characters.

And no, there's really no way to avoid iterating over the string. How do you expect to tell if there are an equal number without reading each character at least once?

Share this post


Link to post
Share on other sites
If you only have two possible characters then isn't it impossible for a string with an odd length to contain an equal number of the characters? Also if you are counting one at a time and one count is higher then the strings length divided by 2 plus 1, you already know the answer. This could help to "early-out" and avoid having to go through each one.

Share this post


Link to post
Share on other sites
Quote:
Original post by Scet
If you only have two possible characters then isn't it impossible for a string with an odd length to contain an equal number of the characters?

Good point. If this is a C-string however you'd still have to iterate over it to find the length, which would defeat this method because then you'd have to go over it again after finding the length if the length turns out to be even.

Quote:
Original post by Scet
Also if you are counting one at a time and one count is higher then the strings length divided by 2 plus 1, you already know the answer. This could help to "early-out" and avoid having to go through each one.

If this thing really has to be optimized (which I doubt) then I would say that this approach could potentially be slower if that isn't often the case due to the extra comparison. It would also be slower on C-strings because you'd have to iterate twice to find the length and then go over each character... same as above.

Share this post


Link to post
Share on other sites
If you really need to optimize you could cast the char * string to a int32 * (or even int64 * on 64-bit platforms), and access the string 4 bytes at a time. Some handy bit-shifting (and perhaps a lookup table) would allow you to count a's vs b's pretty quickly.

Almost certainly not worth the trouble, however.

Geoff

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this