Return to Snippet

Revision: 16425
at August 3, 2009 23:17 by bingjian


Initial Code
/*
Write an efficient function that deletes characters from a string.
Use the prototype:
  string removeChars(string str, string remove);
where any character existing in {remove} must be deleted from
{str}. Justify any design decisions you make and discuss the
efficiency of your solution.

Algorithm outline O(m+n):
1. Set all the elements in your lookup array to false.

2. Iterate through each character in remove, setting the
corresponding value in the lookup array to true.

3. Iterate through str with a source and destination index, copying
each character only if its corresponding value in the lookup array
is false.
*/

string removeChars(string str, string remove){
     char[] s = str.toCharArray();
     char[] r = remove.toCharArray();
     bool[] flags = new bool[128]; //assume ASCII!
     int len = s.Length;
     int src, dst;

     //Set flags for characters to be removed
     for (src=0; src<len; ++src){
        flags[r[src]] = true;
     }
     src = 0; dst = 0;
     //Now loop through all the characters,
     //Copying only if they are not flagged
     while (src<len){
        if (!flags[(int)s[src]]) { s[dst++] = s[src];}
        ++src;
     }
     return new string(s,0,dst);
}

Initial URL


Initial Description


Initial Title
Remove specified characters from a string

Initial Tags


Initial Language
C++