O(n) Using Arrays without sorting

Unreal Courses Talk
,
#1

Something like this would be I believe O(n). However the lecture did not cover the topic of memory usage/overhead usually in this scenario you can pick one over the other an array of 26 ints is not too bad of memory usage as far as I can tell on a modern computer. This approach will use more memory but will have higher speed in theory. Basically the code is as follows the idea is we convert the Ascii code of the letter to a 0 index array value and increment the array for the corresponding letter. If you attempt to increment a non-zero index value you can break knowing you have discovered something that is not an isogram. This would be very similar to doing a hash key on the letter and if a collision exists you do not have an isogram. Okay a couple gotchas: there is no error checking or validation done in here for non-letters or checks for only lowercase, so could have a segfault.

bool FBullCowGame::IsIsogram(FString Guess )
{
    const int32 ASCII_CODE_FOR_A = 97;
    int32 Alphabet[26] = {}; // Initialize array to 0 for all 26 letters
    for(int32 i = 0; i < Guess.length(); i++)
    {
        int32 LetterAsciiCode = Guess[i];
        int32 NormalizedIndex = LetterAsciiCode - ASCII_CODE_FOR_A;
        if(0 == Alphabet[NormalizedIndex])
        {
            Alphabet[NormalizedIndex]++;            
        }
        else
        {
            return false;
         }
    }
    return true; 
}
1 Like
#2

Very nice implementation. Clearly very fast and efficient. Let’s hope the user doesn’t enter Unicode.

#3

I was thinking about that too. Doing some searching. I think it would be perfectly fine http://www.ssec.wisc.edu/~tomw/java/unicode.html
Unicode has the same integer values as ascii. Now I would have to add validation to only allow lowercase letters.

1 Like
#4

Hey, pretty sweet! That was just my first idea :slight_smile:.
Guess one has to have some experience with arrays etc. to get to this solution by himself.

#5

NIce! I just posted something similar but I didn’t know you could initialize the array to zeroes like that, that’s great to know. If you wanted to avoid having to hardcode the ASCII value for ‘a’, you could static_cast(‘a’).

#6

Hello @Disciple_of_One,

very nice implementation. Very sophisticated.

Cheers
Kevin

Privacy & Terms