151、反轉字符串中的單詞

題目描述

給你一個字符串 s ，請你反轉字符串中單詞的順序。

單詞是由非空格字符組成的字符串。s 中使用至少一個空格將字符串中的單詞分隔開。

返回單詞順序顛倒且單詞之間用單個空格連接的結果字符串。

注意：輸入字符串 s中可能會存在前導空格、尾隨空格或者單詞間的多個空格。返回的結果字符串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。

要求：空間復雜度為O(1)；

思路

1. 去除多余空格:收尾無空格，單詞之間只有一個空格

• 定義快慢指針，快指針負責尋找正確的元素，慢指針負責從頭開始給字符串賦值。

2. 反轉字符串
3. 反轉單個單詞

代碼

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;}
};

優(yōu)化【去除多余空格函數】之后的代碼：

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;}
};

時間復雜度：O(n)；
空間復雜度：O(1)；原地修改字符串。

本題反思

• 對于字符串的操作類似于數組，也是利用雙指針查找正確元素然后進行覆蓋操作達到修改字符串的目的。
• 尋找正確字符的過程就是去除多余空格的過程。
• 比起整體反轉字符串，加入了在整體字符串中反轉其中的單詞，這需要額外添加條件判斷。