Delete each character in one string that matches any character in another

Question

I am trying to solve an exercise in which I am given the following function:

/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
 int i, j;

 for (i = j = 0; s[i] != '\0'; i++)
     if (s[i] != c)
       s[j++] = s[i];
 s[j] = '\0';
} 

the exercise is:

Write an alternative version of squeeze(s1,s2) that deletes each character in s1 that matches any character in the string s2.

I have came up with this:

#define COPY   1
#define NOCOPY 0

void multisqueeze(char s[], char f[])
{
int i, j,k, state;
i = j = k = 0;
state = COPY;
while (s[i] != '\0')
{
    state = COPY;
    while (f[k] != '\0' && state == COPY)
    {

        printf("s is %c, f is %c\n", s[i], f[k]); 
        if (tolower(f[k]) == tolower(s[i]))
        {
            state = NOCOPY;
            printf("Nocopy set \n");
        }
        k++;
    }
    k=0;

    if (state == COPY)
    {
        printf("Copying a character, %c\n", s[i]);
        s[j++] = s[i];
    }
    i++;
}
printf("Loop ended, s is %c\n", s[i]);
s[j] = '\0';
}

This seems to be a valid solution for the problem and outputs the correct answer. But I have been told that the implementation is messy and not readable because of the use of the state variable and that there are more elegant ways of doing it. I have been trying to wrap my head around it for some time and I simply can't see a way to not use the state variable at all. I think this exercise is from The C programming Language by Brian Kernighan and Dennis Ritchie.

Answer 1

What you have is an O(n^2) solution.

But lets look at tidying it up first:

1. Do you really need these macros.
   If you must have them then why not name the variable copy and use the macros TRUE/FALSE

#define COPY   1
#define NOCOPY 0

1. Declaring variables using the comma is lazy and considered bad practice, but you should also use more descriptive variable names. i/j/k do not explain what they are being used for. Also if you function is longer and you need to change it looking for all instances of a variable 'i' may take a while longer because of all the false positives on a search so maintenance wise it is also a bad idea.
   There are a couple of edge cases where the declaration can go wrong. So in general it is just best to stay clear.

int i, j,k, state;

1. You are using a while() loop. But a for(;;) loop would have been neater. It allows initialization test and increment in the same statement. This puts all work done on the k variable in the same place.

    while (f[k] != '\0' && state == COPY)

1. Are you sure you actually want to do this test?

        if (tolower(f[k]) == tolower(s[i]))

1. OK. The heart of the problem. Use of the state variable.
   The reason you have this test is to break out of this while loop and then avoid doing the actual work in the next loop. You already have the failed state information implicitly by the place you are in the loop while testing so all you need to do is break out of the current loop. You do not need to do an explicit test in the condition but just use a break statement.

            state = NOCOPY;

1. So if we re-write your version taking into account my comments we get:

void multisqueeze(char s[], char f[])
{
    int i     = 0;  // Iterate over s[]
    int j     = 0;  // Iterate over s[] as elements are copied (this is the dst)

    for(i = 0; s[i] != '\0'; ++i)
    {
        int k     = 0;                    // Iterate over f[]
        for(k = 0; f[k] != '\0'; ++k)
        {
            if (tolower(f[k]) == tolower(s[i]))
            {
                break;
            }
        }

        if (f[k] != '\0') // Then we never reached the end of the loop
        {                 // This means we found a match in the f[] array
            s[j++] = s[i];
        }
    }
    s[j] = '\0';
}

But there is an O(n) solution.
What you need to do is convert the search of the second string into a single comparison.

Since char is a limited range (0-255) we can swap space for time.
Allocate an array that represents every character possible character. Then we can use this as a way to look-up the existence of a character.

So rather than doing this:

        for(k = 0; f[k] != '\0'; ++k)
        {
            if (tolower(f[k]) == tolower(s[i]))
            {
                break;
            }
        }

for each iteration of s[]. What you want to do is iterate over f[] once and save the state of each character. So that you can just look up the answer in one step rather than an iteration. To do this we hoist this loop out of the inner loop and allocate an array for all possible values of char, then mark any we find in f[] as true in our allocated array.

This is what mine would look like (actually mine would look slightly different as I would have written in the C++ style but I have translated into C to make it consistent with the question).

void squeeze(char s[], char f[])
{
    int   loopF;
    int   loopS;
    int   squeeze   = 0;
    int   test[256] = {0};            // One for each character. Default to false.
                                      // I would use bool here. But C does not have bool
                                      // Could use char to save space but that can be confusing
                                      // as not everybody considers a char as an integer type. 

    for(loopF = 0; f[loopF] != '\0'; ++loopF)
    {    test[tolower(f[loopF])]  = 1;    // Mark every character in test that is in f as true.
         test[toupper(f[loopF])]  = 1;    // Thus we can test for existence just by looking it up
    }

    for(int loopS=0; s[loopS]; ++loopS)
    {
          if (test[s[loopS]])          // Test to see if the character in s is also marked true in test.
          {    squeeze++;
               continue;
          }
          // move characters down the squeezed amount
          s[loopS-squeeze] = s[loopS];
    }
}

Answer 2

I can provide an alternative solution. It does not use any state variable.

void multisqueeze(char s[], char f[]) {
    char *from = s, *to = s, *p;
    for( ; *from; from++ ) {
        for ( p = f; *p; p++ )
            if ( *from == *p )
                break;
        if ( !*p ) {
            *to = *from;
            to++;
        }
    }
    *to = '\0';
}

Answer 3

for long discard string create a lookup

#include <string.h>

void multisqueeze(char *s, char *f)
{
    char mapping[256];
    bzero(mapping, 256);
    for(; *f != '\0'; f++) mapping[*f] = 1;
    char* w = s;
    while (*s != '\0') {
        if (! mapping[*s])
            *w++ = *s;
        s++;
    }
    *w = '\0';
}

Answer 4

Although there are quite a few ways to do this, I think I'd represent the "set" of characters to be skipped as an array of "boolean"s -- which is to say an integer for each possible character, saying whether to copy that character or not:

char copy[CHAR_MAX];

// by default, we copy all characters:
memset(copy, 1, sizeof(copy));

// but we don't copy any that are contained in f:
while (*f)
    copy[*f++] = 0;

Then I'd walk through the string just about like in the original function, but for each character, instead of checking whether that equals c, I'd check whether that item in the copy array was set to 0 or 1. Copy each character if and only if that spot in copy is set to 1 (or at least that it's not 0 -- keep in mind that 0 evaluates to false, and anything else evaluates to true).

Answer 5

A very good solution was given taking into account that there is only 256 chars in C and using an array of finite and acceptable size to perform the comparison in O(1). But if we were in Java (or other Unicode language), or if the problem involves ints or longs instead of chars, representing all possible values in an array can become impractical. To keep the algorithm as fast as possible, a hashtable can be used, keeping the comparison in O(1), but needing more memory. If you are low on memory, this is an algorithm in O(n*log(n)) time complexity and in O(n) memory usage:

1. Sort both input, keeping the original index of the data in temp arrays,
2. Remove the matching data,
3. Sort back by index.