题目描述
输入一个英文句子,单词之前用一个空格隔开,且句首和句尾没有多余空格。
翻转句子中单词的顺序,但单词内字符的顺序不变。
为简单起见,标点符号和普通字母一样处理。
例如输入字符串”I am a student.”,则输出”student. a am I”。
样例
输入:"I am a student."
输出:"student. a am I"
算法
(字符串,双指针算法) $O(n)$
曲线救国,直接做不好做,分两步操作
- 翻转整个字符串
- 翻转每个单词,使用双指针算法扫描每个单词进行翻转
翻转操作调用库函数 reverse()
时间复杂度
翻转整个字符串的时间复杂度为 O(n),翻转每个单词需要遍历整个字符串时间复杂度也是 $O(n)$,所以总时间复杂度为 $O(n)$
C++ 代码
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end());
for (int i = 0; i < s.size(); i ++ )
{
int j = i;
while (j < s.size() && s[j] != ' ') j ++ ;
reverse(s.begin() + i, s.begin() + j);
i = j;
}
return s;
}
};