Coder's Guild Mailing List

Re: Word contains another word

Posted by Dan Nuffer on 1999-09-07

> Hello all!
>
> I'm programming a program that makes anagrams, and I have to
> check if one word contains the letters of another.
>
> Example:
> I need to check if the word MICROSOFT contains the word FOOT.
>
> Any idea how to do this fast? I currently have only simple for-
> loops that go through both words letter by letter and compare
> them.
>

Basic idea: create 2 arrays that contain a count of the number of letters in
each word and then compare to see if the first contains the second.

here's some sample code in C++

bool compare(char* s1, char* s2)
{
    char s1count[256];
    char s2count[256];
    for(int i = 0; i < 256; i++)
        s1count[i] = s2count[i] = 0;

    for(int i = 0; i < strlen(s1); i++)
    {
        s1count[s1[i]]++;
    }
    for (int i = 0; i < strlen(s2); i++)
    {
        s2count[s2[i]]++;
    }

    bool retval = true;
    for (int i = 0; i < strlen(s2); i++)
    {
        retval &= s2count[s2[i]] <= s1count[s2[i]];
    }
    return retval;
}

I just wrote this code now, and haven't tested it, but I *think* it will
work. :)

Later,
Dan

Sponsored by Wrox Press - www.wrox.com. Programmer to Programmer (TM)

| | Timeline | Home