(第12天)【leetcode题解】151、反转字符串中的单词

151、反转字符串中的单词

题目描述

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

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

要求：空间复杂度为O(1)；

思路

去除多余空格:收尾无空格，单词之间只有一个空格

定义快慢指针，快指针负责寻找正确的元素，慢指针负责从头开始给字符串赋值。

反转字符串
反转单个单词

代码

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 slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针// 去掉字符串前面的空格while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {fastIndex++;}for (; fastIndex < s.size(); fastIndex++) {// 去掉字符串中间部分的冗余空格if (fastIndex - 1 > 0 && s[fastIndex] == ' ' && s[fastIndex - 1] == s[fastIndex]) {continue;} else {s[slowIndex++] = s[fastIndex];}}if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格s.resize(slowIndex - 1);} else {s.resize(slowIndex); // 重新设置字符串大小}
}//反转字符串中的单词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;//把start指向下一个单词的开头}}return s;}
};

优化【去除多余空格函数】之后的代码：

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);//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;//把start指向下一个单词的开头}}return s;}
};