[LeetCode] 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".

Clarification:

1.What constitutes a word?
A sequence of non-space characters constitutes a word.

2.Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.

3.How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

• 解题思路1
  • 因为是要得到逆序的单词组合，所以从字符串头部开始遍历，把解析得到的单词放到一个栈中，最后把栈中的单词出栈连接成一个字符串。
  • 遍历过程中，如果某个单词的后面有空格，则在其前面增加一个空格。由于最后一个单词后面也有可能有空格，所以检查最后得到的字符串的第一个字符，如果是空格，则清除它。
• 实现代码1

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/9 11:05
    *  @Status   : Accepted
    *  @Runtime  : 13 ms
******************************************************************/
class Solution {
public:
    void reverseWords(string &s) {
        string temp;
        stack<string> mystack;
        int i = 0;
        while (i < s.size())
        {
            if(s[i] == ' ')
            {
                if (temp.compare(""))
                {
                    //在得到的单词前面增加空格
                    temp.insert(temp.begin(), ' ');
                    mystack.push(temp);  //单词入栈
                    temp = "";  //单词重置为空
                    i++;
                }
                while (i < s.size() && s[i] == ' ')
                {
                    i++;
                }
            }
            else
            {
                temp += s[i];
                i++;
            }
        }
        if (temp.compare(""))
        {
            mystack.push(temp);  //最后得到的单词不为空，则入栈
        }

        s = "";
        while (!mystack.empty())
        {
            s += mystack.top();  //重新组合单词
            mystack.pop();
        }

        if (s.compare("") && s[0] == ' ')
        {
            s.erase(s.begin());  //如果新字符串以空格开头，则清除空格
        }
    }
};

• 解题思路2
  从后往前遍历，遇到空格时单词结束。省去了栈的使用。
• 实现代码2

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/9 14:04
    *  @Status   : Accepted
    *  @Runtime  : 10 ms
******************************************************************/
class Solution {
public:
    void reverseWords(string &s) {
        string result = "";
        string temp = "";
        int i = s.size() - 1;
        while (i >= 0)
        {
            if (s[i] == ' ')
            {
                if (temp.compare(""))
                {
                    temp.push_back(' ');
                    reverse(temp.begin(),temp.end());
                    result.append(temp);
                    temp = "";
                    i--;
                }
                while (i >= 0 && s[i] == ' ')
                {
                    i--; //去除多余空格
                }
            }
            else
            {
                temp.push_back(s[i]);
                i--;
            }
        }
        if (temp.compare(""))
        {
            temp.push_back(' ');
            reverse(temp.begin(),temp.end());
            result.append(temp);
        }

        if (result.size() > 0 && result[0] == ' ')
        {
            result.erase(result.begin()); //去除字符串开头的空格
        }

        s = result;
    }
};