你在与一位习惯从右往左阅读的朋友发消息，他发出的文字顺序都与正常相反但单词内容正确，为了和他顺利交流你决定写一个转换程序，把他所发的消息 message 转换为正常语序。

注意：输入字符串 message 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入: message = “the sky is blue”
输出: “blue is sky the”

示例 2：

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

示例 3：

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

提示：

0 <= message.length <= 10(4)

message 中包含英文大小写字母、空格和数字

可以直接反向获取token，采用双指针获得每一个单词的开头结尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
string reverseMessage(string message) {
string ans;
int len = message.size();
int i = len - 1, j = len - 1;
while (i >= 0) {
while (i >= 0 && message[i] == ' ')
i--;
if (i < 0)
break;
j = i;
while (i >= 0 && message[i] != ' ')
i--;
if (!ans.empty())
ans += " ";
ans += message.substr(i + 1, j - i);
}
return ans;
}
};

类似于词法分析，最后需要把tokens反向拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    string reverseMessage(string message) {
        vector<string> tokens;
        int i = 0;
        int len = message.size();
        while (!getToken(i, message, tokens, len)) {
        }
        if (tokens.empty())
            return "";
        string ans;
        for (int j = tokens.size() - 1; j > 0; j--) {
            ans.append(tokens[j]);
            ans.append(" ");
        }
        ans.append(tokens[0]);
        return ans;
    }
    bool getToken(int &i, string &message, vector<string> &tokens, int &len) {
        string token;
        while (i < len && message[i] == ' ')
            i++;
        while (i < len && message[i] != ' ') {
            token.push_back(message[i]);
            i++;
        }
        if (!token.empty())
            tokens.push_back(token);
        return token.empty();
    }
};