Reverse Words in a String

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

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

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

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.

Force solution, o(n) time & space complexity. AC

// I need a terminal to mark the end of the input string.
// return the original string if it contains only one word
// The string can not be longer than 2^32
// How about multiple spaces between words? Reduce them to a single space
// Could the input string contains leading or trailing spaces? Yes

//o(n) solution, force solution.
class Solution {
public:
    void reverseWords(string &s) {
        //extreme case
        int length = s.size();
        if(length == 0) return ;
        string outputStr;  
        bool isInWord = false;
        int start, end;
        for(int i = s.size() - 1; i >= 0; i--){
            char c = s[i];
            if(c == ' '){
                if(isInWord == false){
                    continue;
                }
                //in word, find the start of word
                else{
                    isInWord = false;
                    start = i + 1;
                    appendStr(outputStr, s, start, end);
                }
            }
            else{
                if(isInWord == false){
                    //find the end of word
                    isInWord = true;
                    end = i;
                }
                else{
                    //in the word
                }
            }
        }
        if(isInWord == true){
            appendStr(outputStr, s, 0, end);
        }
        s = outputStr;
    }
    void appendStr(string& re, string s, int start, int end){
        if(re.size() > 0) re.push_back(' ');
        re.append(s.substr(start, end - start + 1));
    }
};

O(1) in space, O(n) in time solution

Reverse the word in space. Handle the “index” words carefully.

// I need a terminal to mark the end of the input string.
// return the original string if it contains only one word
// The string can not be longer than 2^32
// How about multiple spaces between words? Reduce them to a single space
// Could the input string contains leading or trailing spaces? Yes

//o(1) solution.
class Solution {
public:
    void reverseWords(string &s) {
        int len = s.size();
        int proceedLen = 0;
        int insertIndex = s.size();
        while(proceedLen < len){
            //find a word
            bool isInWord = false;
            int startIndex = -1;
            int index = 0;
            while(proceedLen + index < len){
                char c = s[index];
                if(c == ' '){
                    if(isInWord == false){
                        //pass spaces at the head
                        index++;
                    }
                    else{
                        //find the end of a word
                        thisLength = index - startIndex;
                        break;
                    }
                }
                else{
                    if(isInWord == false){
                        //find the beginning of a word
                        isInWord = true;
                        startIndex = index;
                        index++;
                    }
                    else{
                        //still in the word
                        index++;
                    }
                }
            }
            //trailing spaces
            if(startIndex == -1){
                s.erase(0, index);
                break;
            }
            
            //insert the word at the insertIndex
            s.insert(insertIndex, s.substr(startIndex, index - startIndex));
            
            //insert a space to seperate words
            s.insert(insertIndex, " ");
            
            //erase the parsed word
            s.erase(0, index);
            
            //update relative indexs
            proceedLen += index;
            insertIndex -= index;
        }
        //deal with extra inserted space
        while(s[0] == ' '){
            s.erase(0, 1);
        }
        
    }
};