efficient way to check the duplicate characters from string2 in string1

Discussion in 'C' started by cimon, Oct 17, 2008.

  1. cimon

    cimon New Member

    Joined:
    Feb 9, 2007
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    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 a moderator: Oct 17, 2008
  2. oogabooga

    oogabooga New Member

    Joined:
    Jan 9, 2008
    Messages:
    115
    Likes Received:
    11
    Trophy Points:
    0
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    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".
     
  4. oogabooga

    oogabooga New Member

    Joined:
    Jan 9, 2008
    Messages:
    115
    Likes Received:
    11
    Trophy Points:
    0
    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]);
    }
     
  5. cimon

    cimon New Member

    Joined:
    Feb 9, 2007
    Messages:
    20
    Likes Received:
    0
    Trophy Points:
    0
    thank you everyone
    yeah this definitely has less less complexity, than the previos..which I posted
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice