Remove characters from a string
February 24, 2012
We will write three versions of the function. The first uses classic lisp-style recursion down the cdrs of a list:
; lisp-style recursion down the cdrs of a list
(define (string-remove str match)
(let loop ((ss (string->list str)) (zs (list)))
(cond ((null? ss) (list->string (reverse zs)))
((string-index (car ss) match) (loop (cdr ss) zs))
(else (loop (cdr ss) (cons (car ss) zs))))))
That works, but it seems inefficient to convert to and from lists, and the list manipulations create a lot of garbage. The typical approach used in C programs is to walk the string using pointers:
; c-style walk the string using pointers
(define (string-remove str match)
(let loop ((src 0) (dest 0))
(cond ((= (string-length str) src)
(substring str 0 dest))
((string-index (string-ref str src) match)
(loop (+ src 1) dest))
(else (string-set! str dest (string-ref str src))
(loop (+ src 1) (+ dest 1))))))
Since that manipulates the string in place, there is no garbage, and the function is much faster; that’s the version I wrote during the development of my program. A third version uses combinators in the style of Haskell:
; haskell-style using combinators
(define (string-remove str match)
(list->string
(filter
(complement (right-section string-index match))
(string->list str))))
That’s actually clearer in Haskell, which represents strings natively as lists of characters, eliminating the need to convert back and forth.
We used string-index, complement and right-section from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/dL1Uy4sR. Be aware that MzScheme, which is used at codepad, make strings immutable by default, so the C-style version that operates in-place requires special handling to make the input string mutable. Mutable strings are standard in R5RS; immutable strings are standard in R6RS.
[…] today’s Programming Praxis exercise, our task is to remove all the characters in one string from the other. […]
My Haskell solution (see http://bonsaicode.wordpress.com/2012/02/24/programming-praxis-remove-characters-from-a-string/ for a version with comments):
Clojure:
(fn [s cs] (apply str (remove (set cs) s)))
Perl’s substitution operator (http://perldoc.perl.org/functions/s.html) was intended for just such text manipulation. Here is a one liner which can be run from command line
In a Scheme-like language with string ports one could also write the desired characters into a string port and in the end extract the accumulated string, something like the following (I’m making up the procedure names, but I bet these things can be found in Racket, for example, and I think they will be in R7RS). Java’s StringBuilder is similar.
And of course I made a silliest typo. Should be
(string-find c x)
.Very short in Python:
In Common Lisp, it’s a one-liner…
(defun remove-str (s1 s2) (remove-if #'(lambda (c) (position c s2)) s1))
or destructively…
(defun delete-str (s1 s2) (delete-if #'(lambda (c) (position c s2)) s1))
This is an actual string-port-using Scheme procedure, tested with Chibi.
(It relies on the new letrec* semantics of internal defines.)
PHP CLI Code:
or the C Code:
[…] are many answers to today’s exercise on Programming Praxis which is to remove from a string characters given in another string. I liked […]
Scheme already has the feature in srfi-13 (and srfi-14 for the convenience). Is it cheating?
(string-delete “Programming Praxis” (->char-set “aeiou”)) => “Prgmmng Prxs”
//Method in Java
public String removeChars(String str1,String str2)
{
String temp=””;
int len = str2.length();
for(int i=0;i<len;i++)
{
for(int j=0;j“Prgrmmng Prxs
//removeChars(“how do i sound without vowels”,”aeiou”)==>hw d snd wtht vwls
above method written in java
Of course, we’d prefer a better data structure for l2, like a map, for faster access…
public static String remove(String in1, String in2) {
if (in1 == null || in2 == null) {
return “”;
}
boolean[] bits = new boolean[256];
char[] chares2 = in2.toCharArray();
for (int i = 0; i < chares2.length; i++) {
bits[chares2[i]] = true;
}
char[] chares1 = in1.toCharArray();
for (int j = 0; j < chares1.length; j++) {
if (bits[chares1[j]]) {
chares1[j] = 0;
}
}
return new String(chares1);
}
Java version
public static String remove(String in1, String in2) {
if (in1 == null || in2 == null) {
return "";
}
boolean[] bits = new boolean[256];
char[] chares2 = in2.toCharArray();
for (int i = 0; i < chares2.length; i++) {
bits[chares2[i]] = true;
}
char[] chares1 = in1.toCharArray();
for (int j = 0; j < chares1.length; j++) {
if (bits[chares1[j]]) {
chares1[j] = 0;
}
}
return new String(chares1);
}
Here’s some simple Javascript code that completes the task:
Slightly more general purpose function that works on any iterable:
void remove_from_string(string source, string pattern, string& result){
for(unsigned int i = 0; i != source.length(); i++){
char ch = source.at(i);
int pos = pattern.find(ch);
if(pos == -1){
result.push_back(ch);
}
}
}
string s1 = “Programming Praxis”;
string s2 = “aeiou”;
foreach (char c in s2)
{
s1 = s1.Replace(c, ‘ ‘).Replace(” “,””);
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Remove {
ArrayList characterlist=new ArrayList();
public void problem()
{
try
{
System.out.println(“Enter the first sentence”);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String word1=br.readLine();
System.out.println(“Enter the second sentence/word”);
String word2=br.readLine();
for(int count=0;count<word2.length();count++)
{
if(!present(word2.charAt(count)))
{
characterlist.add(word2.charAt(count));
}
}
int counter=0;
while(counter<word1.length())
{
if(present(word1.charAt(counter)))
{
if(counter==0)
word1=word1.substring(counter+1);
else
{
word1=word1.substring(0,counter)+word1.substring(counter+1);
}
counter–;
}
counter++;
}
System.out.println(word1);
}
catch(IOException ioe)
{
ioe.printStackTrace();
}
}
public boolean present(char ch)
{
for(char c:characterlist)
{
if(ch==c)
return true;
}
return false;
}
}
In python:
# Python program to remove the charachter
# given in second string
# The program will take two string as input
# Objective is to remove the charachters from the first string
# which is determined by second string
def Remove_String(Original_Str, Rem_Chr):
for j in Rem_Chr:
if Original_Str.find(j)!= -1:
Original_Str = Original_Str.replace(j,”)
print(Original_Str)
Remove_String(‘Programming Praxis’, ‘aeiou’)
In Python:
Solution in java