面试题58 - I

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。

• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

注意：本题与主站 151 题相同：https://leetcode-cn.com/problems/reverse-words-in-a-string/

注意：此题对比原题有改动

Solutions

1. straight forward

2. inplace c version

void reverse(char * lo, char * hi) {
    while (lo < hi) {
        char tmp = *lo;
        *lo++ = *hi;
        *hi-- = tmp;
    }
}

char* reverseWords(char* s){
    if (*s == '\0')
        return s;
    char * w = s, * st = s;
    int size = 0;

    while (*s) {
        // copy inplace eagerly
        if (*s != ' ') {
            *w++ = *s++;
            size++;
        }
        else {
            reverse(w - size, w - 1);
            while (*s && *s == ' ')
                s++;
            if (size && *s)
                *w++ = ' ';
            size = 0;
        }
    }
    // if the last word is missed.
    if (*(s - 1) != ' ')
        reverse(w - size, w - 1);
    // reverse the whole rebuilt string.
    reverse(st, w - 1);
    *w = '\0';

    return st;
}

inplace c++ version

class Solution {
public:
    string reverseWords(string s) {
        if (!s.size()) return "";
        auto [w, r, end] = make_tuple(s.begin(), s.begin(), s.end());

        int len = 0;
        while (r != end) {
            if (*r != ' ') {
                *w++ = *r++; len++;
            }
            else {
                reverse(w - len, w);
                while (r != end && *r == ' ')
                    r++;
                if (len && r != end) *w++ = ' ';
                len = 0;
            }
        }
        if (*(r - 1) != ' ')
            reverse(w - len, w);
        reverse(s.begin(), w);

        return {s.begin(), w};
    }
};

or

class Solution {
public:
    string reverseWords(string s) {
        if (!s.size()) return "";
        istringstream ss(s);
        string res, w;
        while (ss >> w) {
            reverse(w.begin(), w.end());
            res += " " + w;
        }
        if (res.size())
            return {res.rbegin(), res.rend() - 1};
        else
            return res;
    }
};