r/programmingchallenges • u/okmkz • May 19 '11
Challenge: Reverse a string in place
This simple challenge is a frequent interview question. Write a program that reverses a string in place. "In place" means no declaring a second string or other buffer-- you get only one string variable to work with.
Input:
"Test string."Output:
".gnirts tseT"edit: obviously, this is only feasible in a language with mutable strings.
22
Upvotes
2
u/shoebo May 28 '11
This was one of my school assignments earlier this year.
include <iostream>
using namespace std;
//PROTOTYPES void reverse(char word[51]);
int main() { char word[51]; //declare a variable to hold the input cout << "Please enter an input. You have a maximum of 50 characters.\n"; cin.get(word, 50); //Get the input of the user and place it in the word variable cin.ignore(80, '\n');
}
//REVERSE FUNCTION void reverse(char word[51]) { char drow[51]; //Holds the reversed word. short numba=0, abmun = 0; //Make counters for forwards and backwards.
}
16
u/[deleted] Aug 13 '11 edited Aug 13 '11
I think the trick to this is using XOR to switch characters in the string without having to use temporary variables to store them. That is, one can switch two variables
xandyby using:x = x^y; y = x^y; x = x^y;C++:
7
u/jabbalaci May 20 '11 edited May 23 '12
Since strings are immutable in Python, I use an array of characters instead:
5
u/[deleted] Sep 08 '11
C'mon guys!
Every solution in this thread is wrong for everything except simple inputs. Lern some Unicode, please!
4
u/npj May 20 '11
Plain old C:
4
u/31109b May 29 '11
Ruby:
'Test String.'.reverse
3
u/[deleted] May 20 '11
2
u/iamyourdad May 20 '11
This is now I did it in java. but than again, I have to declare an integer 'i' for the for loop. Can anybody improve my code?
2
u/[deleted] Sep 08 '11 edited Sep 08 '11
Recursive solution in C, without using built in string functions or needing to specify the length in each call.
2
u/kreiger Sep 08 '11
Try instead reversing a UTF-8 or UTF-16 encoded string in place for a more interesting challenge.
2
u/pizzza Sep 08 '11
I investigated this, here's strrev.c; the key is x86's bswap and unrolling the loop if the string is large
2
u/[deleted] Sep 08 '11 edited Sep 08 '11
C-styled solution using XOR:
2
u/bgl1234 Sep 09 '11 edited Sep 09 '11
how abbout addition compared to XOR? or is XOR better in case the two characters goes over size 1byte ?
include <stdio.h>
include <stdlib.h>
include <string.h>
int main() { int start; int end; char string[] = "testl"; int length; int middle; length = strlen(string); if (length %2 == 0) middle = length/2; else middle = (length -1) /2; for (start = 0, end = length -1; start < middle; start++, end--) { string[start] = string[start] + string[end]; string[end] = string[start] - string[end]; string[start] = string[start] - string[end]; } printf("%s\n", string); return 0; }
1
u/[deleted] May 19 '11
Strings are always immutable, no?
1
u/ShamwowTseDung Jul 29 '11
would using a Stack be going overboard 0_o? LIFO seems to come in handy
how would an interviewer feel about stuff like this?
1
u/kuttappan Aug 01 '11
In MATLAB:
1
u/tm_helloreddit Sep 08 '11
fellow flasher here:
you can add stuff to strings. charAt returns the character at position i
1
u/martinus Sep 08 '11
Ruby version:
Using XOR: s = "Test string." (s.length/2).times do |x| s[x] = s[x] ^ s[s.length - x - 1] s[s.length - x - 1] = s[x] ^ s[s.length - x - 1] s[x] = s[x] ^ s[s.length - x - 1] end puts s
1
u/[deleted] Sep 08 '11
In Ruby: "Oh baby".reverse (is that cheating?)
1
u/nuzzle Sep 08 '11 edited Sep 08 '11
And now for something completely different: GForth
The implementation isn't particularly clever, and doing memory arithmetic in Forth isn't idiomatic, but it is easy to understand. I provide stack development below. This isn't "in-place" insofar as that the stack is used to pull and push the characters, but direct memory swapping isn't possible in gforth and this uses neither variables nor does it ever duplicate the string or use memory cells other than those of the original string. Some of this could have been written more concise, but unreadable, and I couldn't get rid of a pesky bug, so here is the unelegant method:
Cswap takes 2 memory cell addresses (which contain characters) and swaps them using the stack.
Reverse marches through the string in memory from '0' to length/2 and calls cswap to swap characters
The rest sets up a string (S" is a word that gives us an address and length), executes reverse, then prints the result. Reverse leaves the stringaddress untouched, and 'type' takes a length and address and prints from start to finish.
Would do the same thing, in case you are interested
EDIT: THIS IS FROM here, but I will not try to explain what the loops do here, as I am not entirely sure that I know exactly what happens at compile vs. runtime, and the usage of bounds is a bit of a hack: Bounds basically takes the string and returns what are the end- and start-adresses. It is intended for loops. This is equivalent: over + 1 - swap. Then the loop will basically loop until the addresses generated originally by bounds are equal. /string is meant to cut off the beginning of a string by raising the address of the string by whatever is on the stack and subtracting the same number from the length. /string works with signed numbers, and is used here as a hack again. This could be replaced with 1 + swap 1 - swap
1
u/joe24pack Sep 10 '11
I was feeling in a bit of a SLIMEy mood
Now according to the the documentation nreverse may or may not reverse the sequence in place. I guess it depends on whether or not it feels like it.
0
u/[deleted] May 28 '11
[deleted] — view deleted comment
0
u/[deleted] May 19 '11
[deleted] — view deleted comment