Posted By

bingjian on 08/03/09


Tagged

String


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

khouser


Remove specified characters from a string


 / Published in: C++
 

  1. /*
  2. Write an efficient function that deletes characters from a string.
  3. Use the prototype:
  4.   string removeChars(string str, string remove);
  5. where any character existing in {remove} must be deleted from
  6. {str}. Justify any design decisions you make and discuss the
  7. efficiency of your solution.
  8.  
  9. Algorithm outline O(m+n):
  10. 1. Set all the elements in your lookup array to false.
  11.  
  12. 2. Iterate through each character in remove, setting the
  13. corresponding value in the lookup array to true.
  14.  
  15. 3. Iterate through str with a source and destination index, copying
  16. each character only if its corresponding value in the lookup array
  17. is false.
  18. */
  19.  
  20. string removeChars(string str, string remove){
  21. char[] s = str.toCharArray();
  22. char[] r = remove.toCharArray();
  23. bool[] flags = new bool[128]; //assume ASCII!
  24. int len = s.Length;
  25. int src, dst;
  26.  
  27. //Set flags for characters to be removed
  28. for (src=0; src<len; ++src){
  29. flags[r[src]] = true;
  30. }
  31. src = 0; dst = 0;
  32. //Now loop through all the characters,
  33. //Copying only if they are not flagged
  34. while (src<len){
  35. if (!flags[(int)s[src]]) { s[dst++] = s[src];}
  36. ++src;
  37. }
  38. return new string(s,0,dst);
  39. }

Report this snippet  

You need to login to post a comment.