reverse word in a string

leetcode

---

question

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

click to show clarification.

Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
Show Tags

solution 1 - by using extra space as stack

version 1

class Solution
{
public:
    void reverseWords(string &s)
    {
        vector<string> stack;
        string temp_s;
        bool w_boundary = false;
        for( int i = 0; i < s.length(); i++)
        {
            char c = s[i];
            // starting space need to ignre
            if( isspace(c) && !w_boundary)
            {
                continue;
            }
            // if it is the first space after a word
            else if(isspace(c) && w_boundary)
            {
                // need to push the word to stack
                stack.push_back(temp_s);
                // clear the temp string prepare for the next loop
                temp_s.clear();
                // push a space to sperator
                stack.push_back(" ");
                // reset it to be false, it goes to the above if block
                // extra space would be ignored
                w_boundary = false;
            }
            else if( isalnum(c) )
            {
                if(!w_boundary)
                {
                    w_boundary = true;
                }
                temp_s += c;
            }
        }
        // cleare the origina string
        s.clear();
        while(!stack.empty())
        {
            s.append(stack.back());
            stack.pop_back();
        }
    }
};

result :

Input: "a"
Output: ""
Expected: "a"

version 2

class Solution
{
public:
    void reverseWords(string &s)
    {
        vector<string> stack;
        string temp_s;
        bool w_boundary = false;
        for( int i = 0; i < s.length(); i++)
        {
            char c = s[i];
            // starting space need to ignre
            if( isspace(c) && !w_boundary)
            {
                continue;
            }
            // if it is the first space after a word
            else if(isspace(c) && w_boundary)
            {
                // need to push the word to stack
                stack.push_back(temp_s);
                // clear the temp string prepare for the next loop
                temp_s.clear();
                // push a space to sperator
                stack.push_back(" ");
                // reset it to be false, it goes to the above if block
                // extra space would be ignored
                w_boundary = false;
            }
            else if( isalnum(c) )
            {
                if(!w_boundary)
                {
                    w_boundary = true;
                }
                temp_s += c;
                if(i==s.length()-1)
                {
                    stack.push_back(temp_s);
                }
            }
        }
        // cleare the origina string
        s.clear();
        while(!stack.empty())
        {
            s.append(stack.back());
            stack.pop_back();
        }
    }
};

after adding this code :

if(i==s.length()-1) {
stack.push_back(temp_s); }

result :

version 3

vector<string> stack;
        string temp_s;
        bool w_boundary = false;
        for( int i = 0; i < s.length(); i++)
        {
            char c = s[i];
            // starting space need to ignre
            if( isspace(c) && !w_boundary)
            {
                // if there is trailing space
                // the below code would push an extra space
                // should be poped here
                if(i==s.length()-1)
                {
                    stack.pop_back();
                }
                continue;
            }
            // if it is the first space after a word
            else if(isspace(c) && w_boundary)
            {
                // need to push the word to stack
                stack.push_back(temp_s);
                // clear the temp string prepare for the next loop
                temp_s.clear();
                // push a space to sperator
                stack.push_back(" ");
                // reset it to be false, it goes to the above if block
                // extra space would be ignored
                w_boundary = false;
            }
            else if( isalnum(c) )
            {
                if(!w_boundary)
                {
                    w_boundary = true;
                }
                temp_s += c;
                if(i==s.length()-1)
                {
                    stack.push_back(temp_s);
                }
            }
        }
        // cleare the origina string
        s.clear();
        while(!stack.empty())
        {
            s.append(stack.back());
            stack.pop_back();
        }
    }

result :

runtime error
Last executed input: " "

version 4

vector<string> stack;
        string temp_s;
        bool w_boundary = false;
        for( int i = 0; i < s.length(); i++)
        {
            char c = s[i];
            // starting space need to ignre
            if( isspace(c) && !w_boundary)
            {
                // if there is trailing space
                // the below code would push an extra space
                // should be poped here
                if(i==s.length()-1&&!stack.empty())
                {
                    stack.pop_back();
                }
                continue;
            }
            // if it is the first space after a word
            else if(isspace(c) && w_boundary)
            {
                // need to push the word to stack
                stack.push_back(temp_s);
                // clear the temp string prepare for the next loop
                temp_s.clear();
                // push a space to sperator
                if(i!=s.length()-1)
                {
                    stack.push_back(" ");
                }
                // reset it to be false, it goes to the above if block
                // extra space would be ignored
                w_boundary = false;
            }
            else if( isalnum(c) )
            {
                if(!w_boundary)
                {
                    w_boundary = true;
                }
                temp_s += c;
                if(i==s.length()-1)
                {
                    stack.push_back(temp_s);
                }
            }
        }
        // cleare the origina string
        s.clear();
        while(!stack.empty())
        {
            s.append(stack.back());
            stack.pop_back();
        }
    }

result:

Input: "hi!"
Output: ""
Expected: "hi!"

version 5

 void reverseWords(string &s)
    {
        vector<string> stack;
        string temp_s;
        bool w_boundary = false;
        for( int i = 0; i < s.length(); i++)
        {
            char c = s[i];
            // starting space need to ignre
            if( isspace(c) && !w_boundary)
            {
                // if there is trailing space
                // the below code would push an extra space
                // should be poped here
                if(i==s.length()-1&&!stack.empty())
                {
                    stack.pop_back();
                }
                continue;
            }
            // if it is the first space after a word
            else if(isspace(c) && w_boundary)
            {
                // need to push the word to stack
                stack.push_back(temp_s);
                // clear the temp string prepare for the next loop
                temp_s.clear();
                // push a space to sperator
                if(i!=s.length()-1)
                {
                    stack.push_back(" ");
                }
                // reset it to be false, it goes to the above if block
                // extra space would be ignored
                w_boundary = false;
            }
            else if( isword(c) )
            {
                if(!w_boundary)
                {
                    w_boundary = true;
                }
                temp_s += c;
                if(i==s.length()-1)
                {
                    stack.push_back(temp_s);
                }
            }
        }
        // cleare the origina string
        s.clear();
        while(!stack.empty())
        {
            s.append(stack.back());
            stack.pop_back();
        }
    }
    bool isword( char c )
    {
        return !isspace( c ) && !iscntrl( c );
    }

finally passed<, but the speed is not that good.

solution 2 - directly do it in place.

"this is the blue sky"

• firstly reverse each word "siht si eth eulb yks"
• then reverse the whold sentence: "sky blue the is this"

but be aware of that we need to remove the leading and traling space

Here is the my latest code:

#include <iostream>
#include <stdio.h>
#include <sstream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cctype>
#include <utility>
#include <functional>
#include <iterator>
using namespace std;
class Solution
{
public:
    void reverseWords(string &s)
    {
        if(s.length()==0)
        {
            return;
        }
        // 2 pointers
        int prev =0, next= 0;
        // remove the leading space
        while(isspace(s[prev]))
        {
            // this is wrong to increment it, you start remove from start
            //  after remove one, you still need to stay at start
            //s.erase(prev++,1);
            s.erase(prev,1);
        }
        // remove the trailing space
        next = s.length() - 1;
        while(isspace(s[next]))
        {
            s.erase(next--,1);
        }
        // reset the pointers
        prev=next=0;
        while(next != s.length())
        {
            // detect the word boundary, until the next pointer goes to a space
            while(next<s.length()&&!isspace(s[next]))
            {
                next++;
            }
            // reverse the word
            reverse(s.begin() + prev, s.begin() + next);
            if(next == s.length())
            {
                break;
            }
            // erase the additional space between word
            // need to keep one space
            next++;
            while(next<s.length()&&isspace(s[next]))
            {
                s.erase(next,1);
            }
            // prev the new start of the word
            prev = next;
        }
        // the revese the whole sentense
        reverse(s.begin(),s.end());
    }
};
int main()
{
    Solution sol;
    string s = "     this    is the blue sky   hot     ";
    // string s = "     this    is the blue ";
    string s2= "   a   b        ";
    string s3 = "a ";
    string s4 = " ";
    string s5 = "hi!";
    string s6 ="b ";
    string s7 ="";
    string s8 ="ab";
    sol.reverseWords( s );
    cout <<"."<< s <<"." <<endl;
    sol.reverseWords( s2 );
    cout << s2 <<endl;
    sol.reverseWords( s3 );
    cout << s3 <<endl;
    sol.reverseWords(s4);
    cout << s4 <<endl;
    sol.reverseWords(s5);
    cout << s5 <<endl;
    sol.reverseWords(s6);
    cout << s6 <<endl;
    sol.reverseWords(s7);
    cout << s7 <<endl;
    sol.reverseWords(s8);
    cout << s8 <<endl;
    return 0;
}

2 things need to be noticed:

if(next == s.length())
{
break;
}

you can not miss this code, assume you have
" this is blue "
after remove leading and trailing space, u would get :
"this is blue"
when prev -> 'b', next -> 'e' , next pointer already reache the end of string, at line 57, next++ again, next currently = s.length(), if there is no such a check, then the code would go to 67, then 73, and fall into a infinite loop.

here is the new result :

just 13ms. a lot better.