K&R Exercise 2-4

Question

I'm learning how to write programs in C using the k&r book (The C Programming Language) and I have a problem with one of the exercises. It's asking me to detect and remove a character in string s1, which matches any characters in the string s2.

So, say s1 = "A";

And s2 = "AABAACAADAAE"

I want it to return "BCDE"

I know I'm on the right path towards it, i just don't know how to design programs very well, could you give me any additional tips. I tried to read about the binary search tree algorithm, but felt it was a little too advanced for this mundane task.

Thanks everyone!

/* An alternate version of squeeze(s1, s2) that deletes each character in
 * s1 that matches any character in the string s2
 *
 * [email protected]
 */

#include <stdio.h>
#include <string.h>

void squeeze(char s[], char t[]);

char string[] = "BAD";
char sstring[] = "ABC";

int
main(void)
{
    squeeze(string, sstring);
    return 0;
}

void
squeeze(char s[], char t[])
{
    int i, j, d;

    d = 0;
    if(strstr(s, t) == NULL)
        printf("%c", s[i]);
    s[j] = '\0';
}

Answer 1

You don't need a fancy binary search to do the job. What you need is a double for loop that check for occurrence of each char in one string in another, and copy the non-occurring chars into a third char array (which is your result).

Code can be something like the following (not tested!):

char *s1, *s2, *result; /* original strings and the result string */
int len1, len2; /* lengths of the strings */
for (i = 0; i < len1; i++) {
   for (j = 0; j < len2; j++) {
     if (s1[i] == s2[j]) {
       break;
     }
   }
   if (j == len2) {  /* s1[i] is not found in s2 */
     *result = s1[i]; 
     result++; /* assuming your result array is long enough */
   }
}

Answer 2

Great book. If I were you, I would proceed exactly as for the squeeze() in section 2.8, but instead of a direct comparison (s[i] != c) I would write and exploit a function

 int contains(char s[], int c)

which returns 1 if the string s contains c, 0 otherwise. Start with the simple approach; when it works you may improve performance with more complex solutions (binary search, but note that the problem doesn't require the characters in s2 to be in a particular order).

Answer 3

A binary search is way overkill for this. You need three indices. One index (i) to walk through s, one index (k) to walk through t, and one index (j) to keep track of where you are in s for the characters that you need to keep because they are not in t. So, for each character in s, check and see if it is in t. If it is not, keep it in s.

void squeeze(char *s, char *t) {
    int i, j, k;
    int found = 0;

    for(i = j = 0; s[i] != '\0'; i++) {
        found = 0;
        for(k = 0; t[k] != '\0' && (found == 0); k++) {
            if(t[k] == s[i]) {
                found = 1;
            }
        }

        if(found == 0) {
            s[j++] = s[i];
        }

    }

    s[j] = '\0';
}