Advanced Search

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++