aspose file tools*
The moose likes Programming Diversions and the fly likes How to reverse a String without using length Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "How to reverse a String without using length" Watch "How to reverse a String without using length" New topic
Author

How to reverse a String without using length

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
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!!
Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1132
    
  59

I came up with a couple of solutions.


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


Tim Driven Development
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
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
Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1132
    
  59

With recursion
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4422
    
    8

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.

Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1132
    
  59

How about some more recursion with a more Functional Programming approach.
Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1132
    
  59

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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
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?
Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1132
    
  59

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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
I was keeping quiet, since I think that isEmpty() is probably implemented as
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
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.
Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1132
    
  59

Campbell, indeed it is.:

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

(Taken from my JDK 1.7 source.)
Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1132
    
  59

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


Dammit!!!
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4422
    
    8

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.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4422
    
    8

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
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
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.
Claudiu Chelemen
Ranch Hand

Joined: Mar 25, 2011
Posts: 71

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
Ashley Bye
Ranch Hand

Joined: Jan 30, 2013
Posts: 46

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.


"Twenty years from now you will be more disappointed by the things you didn't do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails. Explore. Dream. Discover." - Mark Twain
Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 650
    
  11
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



Ashley Bye
Ranch Hand

Joined: Jan 30, 2013
Posts: 46

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.
Aki Mohan
Ranch Hand

Joined: Aug 22, 2013
Posts: 77

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!
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18669
    
    8

A variant on one of Tim's recursive methods:


Tim Cooke
Bartender

Joined: Mar 28, 2008
Posts: 1132
    
  59

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.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: How to reverse a String without using length