[Webinar] Streamline your web hosting managementRegister Today

x
?
Solved

how can I reverse a string with out using any extra memory

Posted on 2006-04-18
6
Medium Priority
?
572 Views
Last Modified: 2008-01-16
how can I reverse a string with out using any extra memory, thx

example in any programming langueages is fine..
0
Comment
Question by:musclejack
  • 2
  • 2
  • 2
6 Comments
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 16479179
I only think this is possible if the string is a static length. Otherwise, you'd have to use _some_ extra memory (such as integer's for iteration).
0
 
LVL 25

Expert Comment

by:InteractiveMind
ID: 16479281
I also doubt that this can be done without creating new variables on the lower level.

For example, in Java, you could probably pull this off, but what really goes on under the hood, when you [for example] call the substring() function will result in more memory being used temporarily..

So, I think you need to be much more specific here.
0
 
LVL 14

Accepted Solution

by:
dlwyatt82 earned 2000 total points
ID: 16479309
InteractiveMind has a point... using *any* temporary variable of any type (even integers or pointers) would technically use extra memory.  I will assume that you meant "without creating a copy of the string".  Here's a C example, which is probably the simplest example utliizing char pointers:

char * str = strdup("Reverse me!");

char * p1 = str;
char * p2 = str;

while (*p2 != '\0') { p2++; }
p2--;

while (p2 > p1) {
  char tmp = *p2;
  *p2 = *p1;
  *p1 = tmp;
  p2--;
  p1++;
}

printf("Reversed string: %s\n", str);
free(str);
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
LVL 23

Expert Comment

by:brettmjohnson
ID: 16479748
This is a common academic programming assignment, so I won't post the complete code.
dlwyatt82, has posted a brute-force version that does use extra memory ( the char tmp ).

Here is a very big hint:  consider using bitwise XOR on the characters of the string.
0
 
LVL 23

Expert Comment

by:brettmjohnson
ID: 16489441
As I mentioned, it is possible to do this assignment without creating a copy of the string, AND without using temporary variables.  I know for a fact that when this assignment is given, the use of temporary variables is "extra memory".  So dlwyatt82's "assumption" is false, and his solution is incorrect.  So if you copy someone else's [incorrect] work and submit it as your own, you will get the grade you deserve.
0
 
LVL 14

Expert Comment

by:dlwyatt82
ID: 16489559
And your "assumption" that I have misunderstood his requirements may also be false.  Quite frankly, even allocating a pointer consumes "extra memory".

Would it have been any different if I chose to use the address of the null character at the end of the string to hold the characters during the swap?  Now there is no "char tmp" on the stack, but I'm still using 2 or 3 temporary char pointers (which take up as much or more memory as the char itself).

You're right, it's possible this may be an academic assignment where a professor is looking specifically for the answer of using XORs to reverse the contents of two binary variables.  But even then, you have to use SOME sort of temporary storage while you enumerate over the string.  And quite frankly, assignments like this (if the prof is looking for only one correct answer) are just a way to doom honest students to failure, while those who know how to use Google can copy down the answer.  Most people don't come up with these bitwise arithmetic tricks on their own.
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will inform Clients about common and important expectations from the freelancers (Experts) who are looking at your Gig.
Make the most of your online learning experience.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

590 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question