Thursday, January 24, 2008

[Algorithm] Reverse words in a string

This is an interview problem. Given a string, such as "tell me something", output the string as "something me tell", i.e. reverse every word in the string. Here is a demo program in C code, it's easy to understand with the comments given in the code. The basic idea is, scan the string from the end, find the beginning and the end of each word, then write to a temporary buffer.





#include <iostream.h>
#include <stdlib.h>
#include <string.h>

void ReserveWordsInString(char string1[])
{
// get the length of the input string
int length=0;
while (string1[length]!='\0')
length++;
// allocate memory space for a temporary buffer, used to store the temporary result
char *buffer= (char *)malloc(length+1);

// declare four indicators
// MoveInd: from length to 0, used to traverse the input string
// EndInd: indicate the end of a word that is to be reversed in the input string
// BeginInd: indicate the begin of the word that is to be reversed in the input string
// WriteInd: the indicator of the writing position in the temporary buffer
int MoveInd, BeginInd, EndInd, WriteInd;
// initialize the MoveInd to the end of the input string, WriteInd to the begin of the temporary buffer
MoveInd = length-1;
WriteInd = 0;

while (MoveInd>=0)
{
if (string1[MoveInd]!=' ') // if it's a word charactor
{
EndInd=MoveInd;
// scan the current word, find the next non-word charactor
while(MoveInd>=0 && string1[MoveInd]!=' ')
{
MoveInd--;
}
// copy the word to the temporary buffer
for (BeginInd=MoveInd+1; BeginInd <= EndInd; BeginInd++, WriteInd++)
{
buffer[WriteInd]=string1[BeginInd];
}

}
else
{
// write the non-word charactor directly to the temporary buffer
buffer[WriteInd++]=string1[MoveInd--];
}
}
// it is better to append \0 to the end of the buffer
buffer[length]='\0';

// copy the buffer to the input string for output
for (int i=0; i<length; i++)
string1[i]=buffer[i];

// free the allocated memory for the buffer
free(buffer);
}
void main()
{
char string1[]="This is a C program, for word reverse.";
// this is a tricky method in getting the size of an array, explanation is below the code
int length = sizeof(string1)/sizeof(string1[0]);

// Call the function
ReserveWordsInString(string1);

// output the result
for (int i=0; i<length; i++)
{
cout<<string1[i];
}
cout<<endl;
}





Notes: In this program, we encountered a problem, how to get the length of an array or a string?

A well-known and tricky method is to use "sizeof(array)/sizeof(array[0]);", this works in the main program. However, if the array is the input argument of a function, this one doesn't work. Because in this case, the type of the array identifier "decays" into a pointer to the base type, and its value is set to the address of the first element in the array.
So, my opinion is, always traversing the array from the beginning to the end to get the length, like "for(int i=0; array[i]!='\0'; i++)".

A more decent algorithm is: first reverse the whole string in characters, e.g. reverse "tell me something" to "gnihtemos em llet", then using the similar method as above to locate the beginning and end of each word, then reverse each word in characters, e.g. reverse "gnihtemos" to "something". This is an in-place method, which avoids using the extra temporaray buffer.

3 comments:

Anonymous said...

thanks for sharing this site. you can download lots of ebook from here


http://feboook.blogspot.com

Anonymous said...

I am the sort of guy who enjoys to taste hot things. Currently I'm making my personal pv panels. I'm making it all by myself without the aid of my staff. I am utilizing the net as the only path to acheive that. I encountered a very brilliant site which explains how to make pv panels and wind generators. The website explains all the steps needed for solar panel construction.

I am not exactly sure about how precise the info given there is. If some guys over here who had experience with these works can have a see and give your feedback in the thread it would be awesome and I'd really treasure it, cauze I really lav [URL=http://solar-panel-construction.com]solar panel construction[/URL].

Thanks for reading this. U guys are the best.

Anonymous said...

I am considering doing a reverse mobile phone look up by going online. I am having all of these cell phone calls by someone who I don't know and am curious who believe that they are calling. Lots of strange texts and also messages are being left on my personal voice mail and its starting to drive me nuts. So, exactly where should i locate these reverse cell phone search sites?