151. Reverse Words in a String

problem description

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

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

• A word is defined as a sequence of non-space characters.

• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.

• You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

algorithm thought

follow up中提到里，如果是c程序员，尝试使用O(1)空间解决。 我寻思cpp程序员应该也行。这里可以利用数组之前的空间，由于这个算法运行之后，字符串大小肯定是小于等于原始字符串大小的。所以，我们们可以在原始字符串上操作，而不需要新开一个字符串。

首先将空格啥的都去掉，得到精简的单词，将单词翻转，最后将得到的字符串翻转

code

class Solution {
public:
    string reverseWords(string s) {
        int begin=0,end=s.size()-1;
        while(s[end]==' ')
            end--;
        int i=0;
        while(s[i]==' ')
            ++i;
        while(i<=end){
            int tmp=begin;
            while(i<=end&&s[i]!=' '){
                s[begin++]=s[i++];
            }
            reverse(s.begin()+tmp,s.begin()+begin);
            if(begin<=end)
                s[begin++]=' ';
            while(i<=end&&s[i]==' ')
                i++;
        }
        s.resize(begin);
        if(s.back()==' ')
            s.pop_back();
        reverse(s.begin(),s.end());
        return s;
    }
};

algorithm analysis

虽然看起来循环挺多的，但是本质只是遍历了一遍字符串，然后翻转一此，如果长度为n，进行的次数应该是3n，时间复杂度O(n)