# 题目
给定一个字符串,逐个翻转字符串中的每个单词。
示例 1:
输入: "the sky is blue"
输出:"blue is sky the"
示例 2:
输入: "hello world!"
输出:"world! hello"
解释:输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:
输入: "a good example"
输出:"example good a"
解释:如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
151. 反转字符串中的单词 - 力扣(LeetCode)
# 分析
可以用反转字符串的思路,我们可以先移除多余空格然后全部反转,再以字符中的空格为分界反转单词
// 时间复杂度: O (n) | |
// 空间复杂度: O (1) 或 O (n),取决于语言中字符串是否可变 | |
class Solution { | |
public: | |
void reverse(string& s, int start, int end){ // 翻转,区间写法:左闭右闭 [] | |
for (int i = start, j = end; i < j; i++, j--) { | |
swap(s[i], s[j]); | |
} | |
} | |
void removeExtraSpaces(string& s) {// 去除所有空格并在相邻单词之间添加空格,快慢指针。 | |
int slow = 0; // 整体思想参考 | |
for (int i = 0; i < s.size(); ++i) { // | |
if (s[i] != ' ') { // 遇到非空格就处理,即删除所有空格。 | |
if (slow != 0) s[slow++] = ' '; // 手动控制空格,给单词之间添加空格。slow != 0 说明不是第一个单词,需要在单词前添加空格。 | |
while (i < s.size() && s[i] != ' ') { // 补上该单词,遇到空格说明单词结束。 | |
s[slow++] = s[i++]; | |
} | |
} | |
} | |
s.resize(slow); //slow 的大小即为去除多余空格后的大小。 | |
} | |
string reverseWords(string s) { | |
removeExtraSpaces(s); // 去除多余空格,保证单词之间之只有一个空格,且字符串首尾没空格。 | |
reverse(s, 0, s.size() - 1); | |
int start = 0; //removeExtraSpaces 后保证第一个单词的开始下标一定是 0。 | |
for (int i = 0; i <= s.size(); ++i) { | |
if (i == s.size() || s[i] == ' ') { // 到达空格或者串尾,说明一个单词结束。进行翻转。 | |
reverse(s, start, i - 1); // 翻转,注意是左闭右闭 [] 的翻转。 | |
start = i + 1; // 更新下一个单词的开始下标 start | |
} | |
} | |
return s; | |
} | |
}; |