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
0
oogabooga's Avatar
Ambitious contributor
Check out strcspn.
0
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".
0
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]);
}
0
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