Intersection of two strings

[Jammie]

Hi,

Could someone tell me if there's a better way of doing this? I was asked this question in an interview and I wrote a piece of code of O(n2).

// This function returns a new string of the common alphabets found in a and b
char* intersection(char*a, char* b)
{
   static char temp[20];
   int i = 0;
   if ( (a==NULL) || (b==NULL))
        exit(0);
   else
    {
         while ( a != NULL)
         {
               if(strchr(b, *a))
               {
                    temp[i] = *a;
                    i++;
                    a++;
               }
         }  
    }

    return temp;
}

Thanks,
Tina

[Tom Gunn]

If the two strings are not sorted, the 'best' way depends on what trade off you want to make. If you want to have a small memory footprint but slower algorithm your way is fine. If you want to have a faster algorithm at the cost of more memory, two histogram tables is a good way:

define sa as array[0..CHAR_MAX] = {0}
define sb as array[0..CHAR_MAX] = {0}

// build the histograms
for x = 0 to a.length
    ++sa[a[x]]
loop

for x = 0 to b.length
    ++sb[b[x]]
loop

// print the unique intersection
for x = 0 to CHAR_MAX
    if sa[x] <> 0 and sb[x] <> 0 then
        print x as char
    end if
loop

In C that comes out to about a 10 line function and it has O(n) time complexity.

[Jammie]

Yes, I agree. Your code takes more memory and runs faster. I still need to figure out if there are other options. I'll give it another try.

Thanks a lot.

Tina

[Tom Gunn]

I still need to figure out if there are other options.

There are other options, but not for two unsorted strings. Most intersection algorithms assume that both sets are sorted and use an algorithm that is both fast and uses little or no extra memory.

[Jammie]

Thanks Tom. I'll read about those algorithms.

Tina