efficient way to check the duplicate characters from string2 in string1

cimon's Avatar, Join Date: Feb 2007
Go4Expert Member
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

Last edited by shabbir; 17Oct2008 at 08:50.. Reason: Code block
oogabooga's Avatar
Ambitious contributor
Check out strcspn.
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
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's Avatar
Ambitious contributor
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's Avatar, Join Date: Feb 2007
Go4Expert Member
thank you everyone
yeah this definitely has less less complexity, than the previos..which I posted