Reverse String Ignoring Special Characters
October 30, 2015
Let’s begin with the program to reverse a string in place, without considering the requirement to ignore special characters. The simple algorithm uses two pointers, one to the left end of the string and one to the right end of the string, swapping the two characters they point to, then moving the pointers one character closer to the other at each step until they meet:
(define (string-reverse! str) (let loop ((lo 0) (hi (- (string-length str) 1))) (cond ((<= hi lo) str) (else (let ((t (string-ref str lo))) (string-set! str lo (string-ref str hi)) (string-set! str hi t) (loop (+ lo 1) (- hi 1)))))))
> (string-reverse! "a!b3c") "c3b!a"
Now it is obvious how to reverse a string while ignoring special characters; ensure that lo
and hi
never point to special characters:
(define (string-reverse! str) (let loop ((lo 0) (hi (- (string-length str) 1))) (cond ((<= hi lo) str) ((not (char-alphabetic? (string-ref str lo))) (loop (+ lo 1) hi)) ((not (char-alphabetic? (string-ref str hi))) (loop lo (- hi 1))) (else (let ((t (string-ref str lo))) (string-set! str lo (string-ref str hi)) (string-set! str hi t) (loop (+ lo 1) (- hi 1)))))))
> (string-reverse! "a!b3c") "c!b3a"
This function is identical to the previous function except that two clauses have been added to the cond
expression, one checking that the lo
character is alphabetic and one checking that the hi
character is alphabetic.
You can run the program at http://ideone.com/Szld2K.
Two solutions in scala.
The first works with the indexes -> complicated, slow
The second is a faster tail recursive solution
Here’s some C++:
And some Haskell:
Haskell:
In Python.
Standard ML solution.
Here is a Common Lisp solution:
As you can see, it’s very simple. We just use a “generic” function that is not restricted to strings, or vectors, but that will work on any sequence (list, vectors, strings), and using any predicate to select the elements to be reversed.
We’ll use Common Lisp generic functions with methods to provide the variants for the various sequence subclasses (and since string is a subclass of vector, it’ll be included in the method for vector).
Also, we provide two versions of the generic function, one destructive and one non-destructive. nreverse-elements-such will reverse the sequence in place, while reverse-elements-such will create a new sequence. Of course, we will reuse the former to implement the later.
I’m learning Julia, at v0.4.0 now. Strings are stored as UTF-8, character length in a string varies, in-place mutation makes no sense. A vector of valid indices is neatly reversed using a bit vector to mark the positions of the alphabetic indices. The resulting index gives the result.
Another Haskell solution. Similar to the Lisp version, we write a reversal function that takes a predicate indicating which elements to reverse and which to leave in their original positions. We then use it to define functions to reverse letters of a string and odd numbers in a list of numbers. (Arguably, the revPred function suffers from a round of code golf. It’s a sickness… :-)
Another, more straight-forward solution…
@fisherro: Nice ingenious solution. We can extend your proxy idea to an outer container of iterators over the inner container, with a suitable iterator class that acts as a proxy for the inner elements. Now we can eg. sort all digits as well as reversing just the alphabetic characters:
@matthew Very nice!
I’m not sure if it is ever practical, but I like the fact that you could use this to std::sort a std::list in-place by proxying through a std::vector.
It occurs to me that my second solution is not guaranteed to work. Because std::transform does not guarantees the order in which it transforms the elements. It should use std::for_each instead.
package reversestring;
public class ReverseString {
static String input = “a!b3c”;
public static void main(String[] args) {
int stringLength = input.length();
int currentAlphaindex = 0;
char currentChar = ‘a’;
String letters = “”;
String output = “”;
int replacementCount = 0;
char[] alpha = new char[stringLength];
int[] alphaIndex = new int[stringLength];
char[] fullText = new char[stringLength];
for (int i = 0; i = 0; i–){
letters = letters + alpha[i];
letters = letters.trim();
}
for(int i = 0; i = 0)){
fullText[alphaIndex[i]] = letters.charAt(replacementCount);
replacementCount++;
}
output = output + fullText[i];
}
System.out.println(“input: ” + input + “\noutput: ” + output);
}
}
Sorry guys, I stuffed the indentation on that one.
attempt number 2
@fisherro: Thanks. I liked that possible use too. Incidentally, I think my iterator operator++ and operator– should return a *this reference rather than a new iterator (and I don’t think the template template parameter is necessary for the inner container).
I wonder if we could define an inner container that iterates over the contents of a UTF-8 string.
Reblogged this on anutech.
@matthew
A UTF-8 iterator might be tricky. My first instinct is to use std::string as the value_type. But the specification wants an iterator’s operator* to return a reference. (And operator-> requires returning a pointer.) Maybe it could be faked with a proxy object?
I think using char32_t has the same issue.
A string_view might work, though. It can point directly to the original bytes.
@matthew
Here’s a rough first pass of an iterator adapter for walking the characters in a UTF-8 string. It would be better as a container adapter. Well…probably a lot about it could be better. ^_^
http://codepad.org/qNmEkqgy
Yes, looks tricky wrapping up UTF-8 in an iterable class. I was musing on the idea of dealing with UTF-8 in-place, and came up with this. It uses the well-known trick for reversing a sequence of blocks in memory by reversing each block individually, then the whole sequence. Seems a waste of electrons to do the full reverse when the outer blocks are the same size so we deal with that specially:
The output is quite pretty:
Probably doesn’t deal with combining characters properly though…