151. Reverse Words in a String

时间:2021-02-21 15:46:45

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.

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.

本题较为复杂,主要在于可能会存在前缀或者多个连在一起的空格,此时要删去多余的空格,这就需要我们用一个cur指针指向新数组的遍历位置,然后一个一个往前复制。

反转可以分为两步,第一步先将整个数组反转,第二步为将每个单词单独反转,则可得到结果。


class Solution {
public:
    void reverseWords(string &s) {
        int cur=0;
        reverse(s.begin(),s.end());
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==' ')
                continue;
            if(cur!=0)
                s[cur++]=' ';
            int j=i;
            while(j<s.size()&&s[j]!=' ')
                s[cur++]=s[j++];
            reverse(s.begin()+cur-(j-i),s.begin()+cur);
            i=j;
        }
        s.resize(cur);
    }
};