Given a string, how do we reverse the words inside the string?
For example if the input string is “this is a test” the output should be “test a is this”.
The algorithm is simple. This can be done in two steps. The first step is to reverse the entire string. In the second step we traverse the string to find the individual words separated by spaces and reverse them.
In the following program I have used C++ STL string instead of a C-style null terminated string. To read a string including spaces I have used getline(cin,str) function. I have also used reverse(str.begin(), str.end()) as a helper function from standard template library for simplicity.
Here is the C++ program.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include < iostream > #include < string > #include < algorithm > | |
using namespace std; | |
void reverseWords(string & str) { | |
//reverse the entire string | |
reverse(str.begin(), str.end()); | |
string::iterator strIt; | |
string::iterator wordBegin = str.begin(); | |
//state = 0 indicates word has ended; 1 indicates scanning word | |
int state = 0; | |
for (strIt = str.begin(); strIt != str.end(); ++strIt) { | |
if ( * strIt == ' ') { | |
state = 0; | |
if (strIt > wordBegin) reverse(wordBegin, strIt); | |
} else { | |
if (state == 0) { | |
state = 1; | |
wordBegin = strIt; | |
} | |
} | |
} | |
//reverse the last word | |
if (strIt > wordBegin) reverse(wordBegin, strIt); | |
} | |
int main() { | |
string strInput; | |
getline(cin, strInput); | |
reverseWords(strInput); | |
cout << strInput; | |
return 0; | |
} |