Removing occurrences of characters in a string

Posted by DmainEvent on Programmers See other posts from Programmers or by DmainEvent
Published on 2012-09-21T00:20:54Z Indexed on 2012/09/21 15:52 UTC
Read the original article Hit count: 261

Filed under:
|

I am reading this book, programming Interviews exposed by John Wiley and sons and in chapter 6 they are discussing removing all instances of characters in a src string using a removal string...

so removeChars(string str, string remove)

In there writeup they sey the steps to accomplish this are to have a boolean lookup array with all values initially set to false, then loop through each character in remove setting the corresponding value in the lookup array to true (note: this could also be a hash if the possible character set where huge like Unicode-16 or something like that or if str and remove are both relatively small... < 100 characters I suppose). You then iterate through the str with a source and destination index, copying each character only if its corresponding value in the lookup array is false...

Which makes sense... I don't understand the code that they use however... They have

for(src = 0; src < len; ++src){
   flags[r[src]] == true;
}

which is turning the flag value at the remove string indexed at src to true...

so if you start out with PLEASE HELP as your str and LEA as your remove you will be setting in your flag table at 0,1,2... t|t|t but after that you will get an out of bounds exception because r doesn't have have anything greater than 2 in it... even using there example you get an out of bounds exception... Am is there code example unworkable?

Entire function

string removeChars( string str, string remove ){
   char[] s = str.toCharArray();
   char[] r = remove.toCharArray();
   bool[] flags = new bool[128]; // assumes 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 aren’t flagged
   while( src < len ){
       if( !flags[ (int)s[src] ] ){
       s[dst++] = s[src];
   }
   ++src;
   }
   return new string( s, 0, dst );
}

as you can see, r comes from the remove string. So in my example the remove string has only a size of 3 while my str string has a size of 11. len is equal to the length of the str string. So it would be 11. How can I loop through the r string since it is only size 3? I haven't compiled the code so I can loop through it, but just looking at it I know it won't work. I am thinking they wanted to loop through the r string... in other words they got the length of the wrong string here.

© Programmers or respective owner

Related posts about interview

Related posts about algorithms