An efficient way that deletes specified characters from a string

Question

For example, given a str of "Stackoverflow is for every one" and remove of "aeiou", the function should transform str to "Stckvrflw s fr vry n".

I have one char array of string: str[] and one char array of chars to be removed:remove[]

My Solution: Loop str[] looking for each in character in remove[]. Shift str[] one place left every-time. I am sure better hack are possible.

Answer 1

I would loop str[] and store each character which doesn't exist in remove[] in a new array (let's say new_str[]). Then swap new_str[] with str[].

Answer 2

If you can afford one more buffer, you can: Loop str[] looking for each in character in remove[], but instead of shift, copy to new array.

Answer 3

Shifting the entire string left one place will make this an O(n^2) algorithm effectively. You can do this in-place, in linear time:

void Remove (char * src, const char * match) {
   char * dest = src;
   for (;;) { 
      char ch = *src++; 
      if (!strchr (match, ch)) *dest++ = ch;  // Copy chars that don't match
      if (!ch) break;                         // Stop when we copy over a null  
   }
}

I'm assuming here that these are null terminated. If this is not the case, then you have to pass in the lengths as well and modify the algorithm appropriately. In particular, you will not be able to use strchr. Just for completeness, here's a version that works with char arrays (not null-terminated).

// Removes from str[] (of length strlen), all chars that are found
// in match[] (of length matchlen). Modifies str in place, and returns
// the updated (shortened) length of str. 
int Remove (char[] str, int srclen, char[] match, int matchlen) {
   int dst = 0, found;
   for (int src = 0; src < srclen; src++) { 
      char ch = str[src];  
      found = 0;           // Search if this char is found in match
      for (int i = 0; i < matchlen && !found; i++) 
         if (match[i] == ch) found = 1;
      if (!found) str[dst++] = ch;
   }
   return dst;
}

And finally, this is as close to O(n) as we are going to get, I guess. I'm assuming 8 bit chars here and building a look-up table so this should run in O(n) + O(m) where m is the length of the match string.

int Remove (char* str, int srclen, char* match, int matchlen) {
   bool found[256];
   for (int i = 0; i < 256; i++) found[i] = 0;
   for (int i = 0; i < matchlen; i++) found[match[i]] = 1; 

   int dst = 0;
   for (int src = 0; src < srclen; src++) { 
      char ch = str[src];  
      if (!found[ch]) str[dst++] = ch;
   }
   return dst;
}

Answer 4

Using regular expressions to find and replace is a more compact solution. Use the GNU C library or find another which has support for regex search and replace. Of course, if the characters vary each time, you'll have to create the regular expression at runtime. If you stick with your current approach, split it up into functions.

I also like Tarydon's approach. Its less work!!

Answer 5

I believe that this is one of those 'classic' puzzles.

In essence, you scan the 'match' string and make a lookup bit table of possible matches.

Then you walk through 'src' once, checking each char against your table.

O(n) time.

Algorithm something like this:

   static char bits[32];  // Not thread-safe, but avoids extra stack allocation
   char * dest = src;
   memset(bits, sizeof(bits), 0);  
   for (; *remove; remove++)
   {
      bitfields[*match >> 3] |= *remove & 7;
   }

   for (;*src; src++) 
   {
      if (!((bits[*src >> 3] & (*src & 7)) == (*src & 7)))
      { 
        *dest++ = *src;
      }
   }

I believe ischr(), isdigit(), isspace(), etc, work similarly to this technique, but their lookup tables are constant.

Answer 6

Here is my version, the if statement is eliminated from the copy-loop:

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

int main( void ){
  unsigned char str[]    = "Stackoverflow is for every one";
  unsigned char remove[] = "aeiou";

  unsigned char table[256] = { [ 0 ... 255 ] = 1 };
  for( unsigned char *r=remove; *r; r++ ){ table[*r]=0; }

  unsigned char *source=str, *dest=str;
  while( (*dest = *source++) ) dest += table[*dest];

  printf( "str: '%s'\n", str );
}