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 03:58.