151.Reverse Words in a String

Tags: Medium String

Links: https://leetcode.com/problems/reverse-words-in-a-string/

---

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

Example1:

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.

---

class Solution {
public:
    string reverseWords(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int pos = 0;
        int n = s.size(); if (!n) return s;
        //去掉首部的空格
        while (s[pos] == ' ') ++pos;
        s = pos >= n ? "" : s.substr(pos);
        //去掉尾部的空格
        pos = s.size() - 1;
        while (pos > 0 && s[pos] == ' ') --pos;
        s = s.substr(0, pos + 1);

        n = s.size(); if (!n) return s;
        reverse(s.begin(), s.end()); //整体翻转字符串，然后翻转每个单词

        int start = 0, end = 0;
        pos = start;
        while (end < n) {
            start = pos;
            while (end < n && s[end] != ' ') {
                s[pos++] = s[end++];
            }
            if (pos < n) s[pos] = ' ';

            reverse(s.begin() + start, s.begin() + pos); //翻转每个单词
            while (end < n && s[end] == ' ') ++end;
            if (end >= n) break;
            ++pos; //pos指向空格后面的字符
        }

        return s.substr(0, pos);
    }
};

不使用额外存储空间。这里只需要注意一点，28行的程序很重要，因为如果不加，考虑：

a bbb   ccccc
翻转后
ccccc   bbb a

因为第一个循环的end最后会指向空格或者这个字符串的末尾，s[pos++] = s[end++]是去掉单词之间连续的空格，那么pos理应指向空格或者字符串的末尾，如果不加上28行，那么pos指向的是字符b，就少了一个空格。

如果还是无法理解，可以自行模拟检验。