151.翻转字符串中的单词 (Medium)*

题目描述*

给定一个字符串，逐个翻转字符串中的每个单词。

说明*

无空格字符构成一个单词。输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶*

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

代码*

使用字符串流处理比较简单。

字符串流原地算法

class Solution {
public:
    string reverseWords(string s) {
        if(s.length() == 0) {
            return "";
        }
        stringstream ss(s);
        string res = "";
        string cur;
        while(ss >> cur) {
            res = cur + " " + res;
        }
        res = res.substr(0, res.length() - 1);
        return res;
    }
};

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        int l = 0, r = s.length() - 1;
        while(l < s.length() && s[l] == ' ') {
            l++;
        }
        while(r >= 0 && s[r] == ' ') {
            r--;
        }
        if(l > r) {
            return "";
        }

        int start = l, end = r;
        while(start <= end) {
            while(s[start] == ' ' && start <= end) {
                start++;
            }
            int right = start;
            while(s[right] != ' ' && right <= end) {
                right++;
            }
            reverse(s.begin() + start, s.begin() + right);
            start = right;
        }
        int tail = l;
        for(int i = l; i <= r; i++) {
            if(s[i] == ' ' && s[i - 1] == ' ') {
                continue;
            }
            s[tail++] = s[i];
        }
        return s.substr(l, tail - l);
    }
};

最后更新: July 23, 2022