LeetCode151 反转字符串中的单词

前言

题目： 151. 反转字符串中的单词
文档： 代码随想录——反转字符串中的单词
编程语言： C++
解题状态： 没思路…

思路

解题的关键点在于先将整个字符串翻转过来。解题思路如下：

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

代码

快慢指针法

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++] = ' ';while (i < s.size() && s[i] != ' ') {s[slow++] = s[i++];}}}s.resize(slow);}string reverseWords(string s) {removeExtraSpaces(s);reverse(s, 0, s.size() - 1);int start = 0;for(int i = 0; i <= s.size(); ++i) {if (i == s.size() || s[i] == ' ') {reverse(s, start, i - 1);start = i + 1;}}return s;}
};

• 时间复杂度： $O(n)$
• 空间复杂度： $O(1)$