How to reverse a String without using length

In this ”beginning Java” thread we looked at ways to reverse a String without using the length method, nor the length of the underlying array, nor any reverse() methods of pre‑existing classes.

The following constructs and similar are not allowed:-The following are permitted however:-I knocked something up in ¼ hour last night which takes Strings as command‑line arguments and prints them backwards. There appear to be at least two ways to do it. Let's see what people can find.

On your marks,
Get set,
GO!!

I came up with a couple of solutions.


I like the first better because it does not rely on Exception handling for flow control.

Mine was similar; I used insert(0, c), too:-As long as nobody says that the equals() method starts by checking lengths (‍), I shall be all right.

java WordReverser "Read JavaRanch :‍)" ieuhfblk837
“Read JavaRanch :‍)” reversed is “): hcnaRavaJ daeR”
“ieuhfblk837” reversed is “738klbfhuei”

I ahd to add some ‍ characters so :‍) didn't appear as

With recursion

How do we feel about things that probably use the length property under the hood somewhere? Here's my attempt: stick everything on a stack and pop it off again.

How about some more recursion with a more Functional Programming approach.

A variation on the last one. If the Java compiler ever supports tail recursion optimisation then this one would win out over the last as it would occupy constant stack space. Although String concatenation is inefficient over using the StringBuilder which I used in one of my other solutions.

OK. That's my lot.

Matthew Brown wrote: . . . stick everything on a stack and pop it off again. . . .

Shows how badly the original Stack class was designed that you didn't use a class called Stack or XXXStack or StackXXX. Shouldn't you use ArrayDeque rather than a linked list?

Matthew Brown wrote:How do we feel about things that probably use the length property under the hood

Probably hard to avoid it. Even Campbell and I's use of string.substring(1) almost certainly calls string.substring(1, string.length()) under the hood too. I have no idea what CharArrayReader does behind the scenes but I imagine it knows the length of it's current buffer which may or may not be the full length of the character array.

I was keeping quiet, since I think that isEmpty() is probably implemented as

I think things using length under the hood are unavoidable. Substring does indeed use the length field of the value array. I used "".equals(text) to avoid using isEmpty for reasons in my last post, but you can only be sure to avoid length by using exceptions.

Campbell, indeed it is.:

Unfortunately using .equals() doesn't get us off the hook either.

(Taken from my JDK 1.7 source.)

Tim Cooke wrote:I have no idea what CharArrayReader does behind the scenes

Dammit!!!

Campbell Ritchie wrote:

Matthew Brown wrote: . . . stick everything on a stack and pop it off again. . . .

Shows how badly the original Stack class was designed that you didn't use a class called Stack or XXXStack or StackXXX. Shouldn't you use ArrayDeque rather than a linked list?

ArrayDeque would have been fine (and may be slightly faster), but they both do the job well.

Obviously, there should be an interface called Stack (instead of the legacy class that extends Vector - I assume part of the problem is that they didn't want to remove that and so what do you call it?), rather than the monolithic Deque interface. If they had that, it doesn't really matter whether you have an XXXStack class that implements it or you let ArrayDeque and LinkedList implement it and use those.

Tim Cooke wrote:A variation on the last one. If the Java compiler ever supports tail recursion optimisation then this one would win out over the last as it would occupy constant stack space. Although String concatenation is inefficient over using the StringBuilder which I used in one of my other solutions.

Interesting (or not) fact: one thing about these approaches that use substring() is that they're much more efficient using Java 6 than Java 7(u6+). It used to reuse the underlying array and use an offset, so substring() was constant time. But that was changed to prevent memory leaks when you take the substring of a very large String...with the drawback that it's now a linear time operation.

http://java.dzone.com/articles/changes-stringsubstring-java-7

They would have to go for the C# naming conventions of IStack for the interface, something like this:-Then you could have LinkedStack and ArrayStack classes, like the two kinds of List.

Matthew Brown wrote: . . . that was changed to prevent memory leaks when you take the substring of a very large String. . . .

That has been discussed here before, as the only sensible justification for new String("rhubarbrhubarb");
Even that has gone.

I'm not really a big fan of regex, however in this case we could use it to get the String's length, and it would be in accordance with the initial specs.



After getting the string's length, the number of possibilities to reverse the string is countless.

Claudiu

I'm not sure if this violates the condition of toArray() or similar, but here goes my attempt.



Edit: Looking back through the topic since I left it and hit post reply, it would seem that my use of `isEmpty()` is not allowed either.

Needed it a couple of weeks ago in ProjectEuler, testing for palindromes:

String c = "WhateverReveTAHw";

boolean isPalindrome = c.toLowerCase().equals(new Stringbuilder(c).reverse().toString.toLowerCase());

Greetz,
Piet

Piet Souris wrote:Needed it a couple of weeks ago in ProjectEuler, testing for palindromes:

String c = "WhateverReveTAHw";

boolean isPalindrome = c.toLowerCase().equals(new Stringbuilder(c).reverse() .toString.toLowerCase());

Greetz,
Piet

Whilst it certainly does the job well, it doesn't meet the condition to not use the reverse() method of String.

Thought about it a lot but couldn't come up with one. BTW very interesting approaches. The most interesting one is how the functional programming approach is applied here. Damn, I could have thought that . Great work, one of the very interesting threads!

A variant on one of Tim's recursive methods:

Matthew Brown wrote:Interesting (or not) fact: one thing about these approaches that use substring() is that they're much more efficient using Java 6 than Java 7(u6+)

That is interesting. I did not know that.