What you have is an O(n^2) solution.
But lets look at tidying it up first:
- 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
- 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;
- 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)
- Are you sure you actually want to do this test?
if (tolower(f[k]) == tolower(s[i]))
- 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;
- 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];
}
}
tolower()? \$\endgroup\$ – Keith Thompson Aug 5 '11 at 23:12