An efficient way that deletes specified characters from a string

algorithm, c, data-structures

Solution

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;
}

Problem

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.

Original source