Introduction
Another popular interview question is, reverse the words in the string. We have seen how to do string reverse, simply by swapping the last character with first. But when it comes to reversing just words in the sentence, we should be careful as we also need to do this in-place. When you do in-place reverse of just words, you might need to move the letter further in the string which is unnecessary and confusing.
Approach
Easy approach is to reverse the whole string using string reverse and then reverse each word one-by-one. I wanted to solve a Google code jam practice problem as well parallel
http://code.google.com/codejam/contest/dashboard?c=351101#s=p1
The above problem requires reversing the words in the strings given as input.
Example:
Input: this is a test
Output: test a is this
How would do this?
Just string reverse the whole string and then reverse each word one-by-one
Intermediate: tset a si siht
Reverse each word: test a is this
Code
char* str_rev_words(char* str)
{
char* result = str;
while(*str != '\0') {
char* tstr = str;
char* istr = tstr; // string start
while(1) {
if(*(tstr+1) == ' ' || *(tstr+1) == '\0') break;
tstr++;
}
char* estr = tstr; // string end
while(!(istr >= estr))
{
char tmp = *istr;
*istr = *estr;
*estr = tmp;
istr++;
estr--;
}
if(*(tstr+1) == '\0')
str = tstr+1;
else
str = tstr+2;
}
return result;
}
#include <fstream>
using namespace std;
void main()
{
char line[1000];
ifstream myfile ("C:\\Works\\cppassignments\\algorithms\\B-large-practice.in");
ofstream outfile ("C:\\Works\\cppassignments\\algorithms\\result.txt");
myfile.getline(line, 1000);
int num_of_cases = atoi(line);
for(int i=1; i<=num_of_cases; i++)
{
myfile.getline(line, 1000);
// doProblem
str_rev(line);
outfile<<"Case #"<<i<<": "<<str_rev_words(line)<<endl;
}
outfile.close();
myfile.close();
}
Important points:
- You must note that not just ‘ ‘ is the separator for the word. When you reach the last word, even ‘\0’ will become the separator.
- BUG FIX: When you are reversing the string using swapping last and first, sometimes, first might go beyond than last so, it should be >= condition.
No comments:
Post a Comment