Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   efficient way to check the duplicate characters from string2 in string1 (http://www.go4expert.com/forums/efficient-check-duplicate-characters-t14590/)

cimon 17Oct2008 06:07

efficient way to check the duplicate characters from string2 in string1
 
Is there any other efficient manner of checking duplicate characters from string2 in string1
Code:

    char st1[6]="mikem";
      char st2[5]="Tame";
      int l1=strlen(st1);
      int l2=strlen(st2);
      int i,j;
     
    for( i=0;i<strlen(st2);i++)
    {
         
            for( j=0;j<l1;j++)
            {  if(st1[j]=='\0')
                continue;
                 
                if(st2[i]==st1[j])
                {   
                    st1[j]='\0';
                }
            }
      }

The above is checking each and every alphabet from st2 and replacing it with null in st1 ,if match is found

Is ther Any other more efficient way , rather than this one

-thank you

oogabooga 17Oct2008 21:50

Re: efficient way to check the duplicate characters from string2 in string1
 
Check out strcspn.

xpi0t0s 18Oct2008 02:54

Re: efficient way to check the duplicate characters from string2 in string1
 
The algorithm you've presented operates in a time proportional to the lengths of the strings multiplied together, which might be O(n^2) (I don't know a lot about O() representation so that could be way off).
What you could do to improve matters is to run through the first string storing the number of times a particular character has occurred in a 26-number array (storing either the count or just whether or not a letter has been encountered, whichever is more relevant). Then just loop through the second string checking the array if that letter has been encountered.
Code:

        int i,flags[26];
        for (i=0; i<26; flags[i++]=0) ;
        char *str1="Hello";
        char *str2="World";
        for (i=0; str1[i]; i++)
                if (str1[i]>='a' && str1[i]<='z') flags[str1[i]-'a']=1;
        for (i=0; str2[i]; i++)
                if (str2[i]>='a' && str2[i]<='z' && flags[str2[i]-'a'])
                        putchar(str2[i]);

This should operate in O(n) time (if I'm correct about O() theory) because it operates in a time proportional to the lengths of the strings added together.
Output of the above is "ol".

oogabooga 18Oct2008 05:34

Re: efficient way to check the duplicate characters from string2 in string1
 
Very nice! That would be hard to beat.
Using tolower() will deal with uppercase letters as well.
Code:

int i, n, flags[26];
char *str1="Hello";
char *str2="World";
for (i=0; i<26; flags[i++]=0)
  ;
for (i=0; str1[i]; i++) {
  n = tolower(str1[i]) - 'a';
  if (n >= 0 && n < 26)
    flags[n] = 1;
}
for (i=0; str2[i]; i++) {
  n = tolower(str2[i]) - 'a';
  if (n >= 0 && n < 26 && flags[n])
    putchar(str2[i]);
}


cimon 18Oct2008 07:11

Re: efficient way to check the duplicate characters from string2 in string1
 
thank you everyone
yeah this definitely has less less complexity, than the previos..which I posted


All times are GMT +5.5. The time now is 16:51.