151、反轉(zhuǎn)字符串中的單詞

題目描述

給你一個(gè)字符串 s ，請你反轉(zhuǎn)字符串中單詞的順序。

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

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

注意：輸入字符串 s中可能會存在前導(dǎo)空格、尾隨空格或者單詞間的多個(gè)空格。返回的結(jié)果字符串中，單詞間應(yīng)當(dāng)僅用單個(gè)空格分隔，且不包含任何額外的空格。

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

思路

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

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

2. 反轉(zhuǎn)字符串
3. 反轉(zhuǎn)單個(gè)單詞

代碼

class Solution {
public://原地反轉(zhuǎn)字符串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); // 重新設(shè)置字符串大小}
}//反轉(zhuǎn)字符串中的單詞string reverseWords(string s) {removeExtraSpaces(s);//去除多余空格reverse(s, 0, s.size() - 1);//原地反轉(zhuǎn)所有字符//開始逐個(gè)反轉(zhuǎn)單詞int start = 0;//指向每一個(gè)單詞的開頭for (int i = 0; i <= s.size(); ++i) {if (i == s.size() || s[i] == ' ') {//到達(dá)空格或字符串尾部，說明一個(gè)單詞結(jié)束，進(jìn)行反轉(zhuǎn)reverse(s, start, i - 1);start = i + 1;//把start指向下一個(gè)單詞的開頭}}return s;}
};

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

class Solution {
public://原地反轉(zhuǎn)字符串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] != ' ') {//如果目前遍歷到的字符不是空格，就進(jìn)行處理if (slow != 0) s[slow++] = ' ';//給每個(gè)單詞之間添加空格while (i < s.size() && s[i] != ' ') {s[slow++] = s[i++];}}}s.resize(slow);//slow的大小就是刪除多余空格后字符串的大小
}//反轉(zhuǎn)字符串中的單詞string reverseWords(string s) {removeExtraSpaces(s);//去除多余空格reverse(s, 0, s.size() - 1);//原地反轉(zhuǎn)所有字符//開始逐個(gè)反轉(zhuǎn)單詞int start = 0;//指向每一個(gè)單詞的開頭for (int i = 0; i <= s.size(); ++i) {if (i == s.size() || s[i] == ' ') {//到達(dá)空格或字符串尾部，說明一個(gè)單詞結(jié)束，進(jìn)行反轉(zhuǎn)reverse(s, start, i - 1);start = i + 1;//把start指向下一個(gè)單詞的開頭}}return s;}
};

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

本題反思

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