Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

[Easy] Shift String

 
Jason Menard
Sheriff
Posts: 6450
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Write a method that given an input String and an integer, returns a new String that is each character of the input String shifted a number of places as indicated by the integer (positive int shifts right, negative int shifts left). The method should have the following signature:
public String shiftString(String s, int n)
For example, if s = "foobar" and n = 1, the method should return "rfooba". If n = -1, the method returns "oobarf". If n = 8, the mehod returns "arfoob".
For more of a challenge, don't use the String functions other than maybe toCharArray().
[ June 27, 2003: Message edited by: Jason Menard ]
 
Anupam Sinha
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's the code
 
Anupam Sinha
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For more of a challenge, don't use the String functions.

Thinking of working on it very soon. But I guess some String functions would be required.
[ June 27, 2003: Message edited by: Anupam Sinha ]
 
Jason Menard
Sheriff
Posts: 6450
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Anupam Sinha:

Thinking of working on it very soon. But I guess some String functions would be required.
[ June 27, 2003: Message edited by: Anupam Sinha ]

Off the top of my head, only toCharArray() comes to mind.
 
Anupam Sinha
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's the code. No checks have been done. For example if null is provided as the input the program will crash.

[ June 27, 2003: Message edited by: Anupam Sinha ]
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's an interesting test to run:

Anupam's first method is much, much faster than the second. It's possible to modify the second method to be much closer to the first in terms of efficiency - but so far I can't find anything that actually beats it. There's probably a useful lesson here about how it's usually best to use standard library functions wherever possible, and keep things simple. Turns out it's also most efficient.
 
Arjun Shastry
Ranch Hand
Posts: 1899
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This also seems to be working but haven't tested efficiency.
 
Jason Menard
Sheriff
Posts: 6450
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My solution:
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK, here was my version:

I figure it toCharArray() was allowec, why not getChars()? That way there's no time wasted copying chars to the wrong position.
Still, performance-wise we can't really beat
or the equivalent
The main advantage these have over any solution that builds a char[] array is that they can take advantage of the new String(StringBuffer) constructor, which is optimized so that it can build a String using the same internal char[] array which the StringBuffer was using. Which is very fast; no new char[] is created, and no copying needs to be done. In comparison, the new String(char[]) constructor is slower because it must make a copy of the char[] for internal use by the String. The reason for this is that String must be immutable; it can't just take a char[] from yyou and assume it will never change. It has to make its own private copy to ensure that it doesn't change.
So, why can a StringBuffer be trusted while a char[] cannot? Because StringBuffer is written so as to pay attention to whether any Strings are sharing its internal char[]. If there are, then if the StringBuffer is subsequently modified it protects the shared char[] by first copying it and then modifying the copy. This means that the previously-shared char[] can now be left to be owned solely by the immatable String class that is using it. So basically, StringBuffer is trusted because the StringBuffer authors have made sure it will never change a char[] that is shared with a String.
 
Timothy Chen Allen
Ranch Hand
Posts: 161
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I realize this has been up here for a while, but I thought I would chime in: my answer doesn't use toCharArray (though it uses charAt):

I like these programming problems. Are there more of those available?
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about:

No "if" tests, no looping through the string, handles abs(amount) larger than string length.
[ July 07, 2003: Message edited by: Stan James ]
[ July 07, 2003: Message edited by: Stan James ]
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmmm, I can put chars.length in the constructor of the StringBuffer for another speed boost. On my T23 this runs in about 0.98 with length, 1.22 without.

Per 60 seconds of testing on a short string (the alphabet once), it beats this:

[ July 07, 2003: Message edited by: Stan James ]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic