• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

How to reverse a String without using length

 
Campbell Ritchie
Sheriff
Pie
Posts: 49472
64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 3080
127
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I came up with a couple of solutions.


I like the first better because it does not rely on Exception handling for flow control.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49472
64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 3080
127
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With recursion
 
Matthew Brown
Bartender
Posts: 4567
8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 3080
127
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about some more recursion with a more Functional Programming approach.
 
Tim Cooke
Sheriff
Pie
Posts: 3080
127
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 49472
64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 3080
127
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 49472
64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was keeping quiet, since I think that isEmpty() is probably implemented as
 
Campbell Ritchie
Sheriff
Pie
Posts: 49472
64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 3080
127
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell, indeed it is.:

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

(Taken from my JDK 1.7 source.)
 
Tim Cooke
Sheriff
Pie
Posts: 3080
127
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tim Cooke wrote:I have no idea what CharArrayReader does behind the scenes


Dammit!!!
 
Matthew Brown
Bartender
Posts: 4567
8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4567
8
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 49472
64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 49472
64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 75
Eclipse IDE Java Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 132
2
Java Mac
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Piet Souris
Rancher
Pie
Posts: 1299
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 132
2
Java Mac
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 99
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 21155
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A variant on one of Tim's recursive methods:


 
Tim Cooke
Sheriff
Pie
Posts: 3080
127
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic