Skip to main content
gamedev.net
🔒 Locked

Reversing Words

Started by BlackDragon Sep 25, 2005 at 10:06 PM 8 replies 1.5k views
Original Post
BlackDragon
BlackDragon
Hello, I took a test today for an interview and I came across a question in which I could not answer. I realy dont have too much of a good idea as to how to solve this problem. Im sure what the question is looking for a good use of pointers. here is the question: Write a C or C++ program to reverse the words in a sentence, in place, without using a 2nd array. The algorithm must operate in linear time (O(n)). As an example, if the original sentence were “”Watch John write a tech test.”” The output should be “”.test tech a write John Watch”” What i have so far is I count the number of words in the sentence. But with out using a 2nd array im not sure how to copy the words with out erasing the other.
chowe6685
chowe6685
Offhand I'd make two passes. The first would reverse the entire sentence, the second would flip each word back the right way - not sure if it's the most efficient method - but it shoud work and wouldn't be too hard to implement.


choffstein
choffstein
EDIT 2: Whoops again. I keep reading this thing wrong. Wow, this is really, really a lot harder than I thought. O(n)? WOW!

EDIT: WHOOPS. Misread the post. But I worked so goddamn hard, I am not about to delete this.

Okay, so here is how I would do it. It would require a couple pointers. They both start at the beginning of the array. The first one stays put, the second continues until it finds a space. The space location is saved. Now use my method as described below to reverse the word, now that we know the start and end. After the word is reversed, set both pointers to the location of the space. Like this...

#include <iostream>using namespace std;int main (int argc, char * const argv[]) {    	char somearray[] = {'t','h','i','s',' ','i','s',' ','a',' ','t','e','s','t','\0'};		char *p = somearray;	char *q = somearray;		while(q < (somearray + 14))	{		char *t;		while( *q != ' ' && q < (somearray + 14)) q++;		t = q; //save the location of the space		q--; //go to the last character		while(q > p) //while we have characters to swap		{			//swap them.			char temp = *p;			*p = *q;			*q = temp;			p++;			q--;		}		t++; //go past the space		p = q = t; //set them both to this location	}		cout << somearray << endl;}


That should work...though, it might be O(n^2)

Basically, you break the big array down into smaller arrays.

Here is a description of the inner loop. You set the pointers at opposite ends of the array, and swap values. Increase the first one, decrease the second one. At some point, the second pointer will be less than the first one, at which point the array is switched.

There are really two cases to think about: Even number of characters and odd. Lets say it is even. Example: abcdef
abcdef   -->  fbcdea  --> fecdba  -->  fedcba --> DONE!  ^ is less than **    ^         *  ^         *^           ^*


Okay, so what about odd?
abcde   -->  ebcda  -->  edcba  -->  DONE!   * and ^ are equal.*   ^         * ^          *                           ^

There is the explaination of how it works.

[Edited by - visage on September 25, 2005 11:31:56 PM]
JohnBolton
JohnBolton
At first I was intimidated by O(n), but really it isn't hard. O(n) doesn't mean 1 pass, it means a constant number of operations per character. To reverse the words takes two passes: first reverse the entire string, then reverse each word.
John BoltonLocomotive Games (THQ)Current Project: Destroy All Humans (Wii). IN STORES NOW!
iMalc
iMalc
Quote:
Original post by visage
	char somearray[] = {'t','h','i','s',' ','i','s',' ','a',' ','t','e','s','t','\0'};
Did you know that the above is exactly the same as:
	char somearray[] = "this is a test";
Yes you can do that!
However it should also really be declared as const too in this case.
snk_kid
snk_kid 
#include <algorithm>#include <string>#include <iostream>int main() {    const char* delimiters = "\t\n ";    std::string s = "    scooby    bar    foo   ";    std::string::size_type index1 = 0, index2 = 0;    const std::string::iterator sbegin = s.begin();    while((index1 = s.find_first_not_of(delimiters, index2)) != std::string::npos) {	if((index2 = s.find_first_of(delimiters, index1)) == std::string::npos)	    index2 = s.length();	std::reverse(sbegin + index1, sbegin + index2);    }    std::reverse(s.begin(), s.end());    std::cout << s << std::endl;}
doynax
doynax
I actually read the exercise this time..
void reverse_string(char *begin, char *end) { while(begin < --end) {  char c = *begin;  *begin++ = *end;  *end = c; }}void reverse_words(char *string) { char *begin, *end = string; while(*end) {  while(isspace(*end)) {   ++end;  }  for(begin = end; !isspace(*end); ++end) {   if(!*end) {    break;   }  }  reverse_string(begin, end); } reverse_string(string, end);}
RunningInt
RunningInt
This one works

void reverseit(char *c) {   char* len;      for (len=c; *len!='\0'; len++){}  //find str length   *len=' ';  //set end char to space so that reversing last word is easier      char*s=c;   char temp;   for (char*p=c; p<=len; p++)  //iterate through string   {      if (*p!=' ') continue;   //find each word      char*v=p-1;      for (char*t=s;t<v; t++,v--)   //reverse word      {        temp=*t,        *t=*v;        *v=temp;      }      s=p+1;   }   *len--='\0';  //replace last char as null      //reverse whole string   for (char*p=c; p<len; p++,len--)   {    temp=*p;    *p=*len;    *len=temp;   }}


INP: "Watch John write a tech test"
OUP: "test tech a write John Watch"

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.