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

難度中等830

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

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

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

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

?

示例 1：

輸入：s = "the sky is blue"輸出："blue is sky the"

示例 2：

輸入：s = " ?hello world ?"輸出："world hello"解釋：反轉(zhuǎn)后的字符串中不能存在前導(dǎo)空格和尾隨空格。

示例 3：

輸入：s = "a good ? example"輸出："example good a"解釋：如果兩個(gè)單詞間有多余的空格，反轉(zhuǎn)后的字符串需要將單詞間的空格減少到僅有一個(gè)。

?

提示：

• 1 <= s.length <= 104

• s?包含英文大小寫(xiě)字母、數(shù)字和空格?' '

• s?中?至少存在一個(gè)?單詞

?

進(jìn)階：如果字符串在你使用的編程語(yǔ)言中是一種可變數(shù)據(jù)類型，請(qǐng)嘗試使用?O(1)?額外空間復(fù)雜度的?原地?解法。

第一種思路：

模擬，當(dāng)字符串的字符不是空格時(shí)，將該字符加入臨時(shí)的單詞中，當(dāng)字符串的字符為空格時(shí)，需要先特判當(dāng)前單詞是否為空，若為空就不加入棧中，否則入棧，最后退出循環(huán)時(shí)再將單詞入棧一次，這次也要特判是否當(dāng)前單詞為空。

最后新開(kāi)一個(gè)答案字符串，將棧中的單詞出棧，按規(guī)律添加空格即可。

時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)

class?Solution?{

public:

????string?reverseWords(string?s)?{

????????stack<string>?ss;

????????string?tmp="";

????????for(int?i=0;i<s.size();i++){

????????????if(s[i]!='?'){

????????????????tmp+=s[i];

????????????}else?if(s[i]=='?'){

????????????????while(s[i+1]=='?'&&i<s.size()-1)i++;

????????????????if(tmp!="")ss.push(tmp);

????????????????tmp="";

????????????}

????????}

????????if(tmp!="")ss.push(tmp);

????????string?ans;int?flag=0;

????????while(!ss.empty()){

????????????if(flag)ans+="?";

????????????ans+=ss.top();

????????????flag=1;

????????????ss.pop();

????????}

????????return?ans;

????}

};

第二種思路：

先將整個(gè)字符串反轉(zhuǎn)

然后用雙指針將字符串中的空格消除：

當(dāng)快指針是非空格并且慢指針不是0時(shí)，就讓慢指針?biāo)诘牡刂窞榭崭瘢缓笞屄羔樦赶虻淖址扔诳熘羔樦赶虻淖址?，知道快指針等于空格為止，注意：快指針在這個(gè)內(nèi)層循環(huán)中不能超出字符的總數(shù)量，最后將字符串的大小調(diào)整為slow的大小

將每個(gè)單詞逐個(gè)反轉(zhuǎn)

時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

class?Solution?{

public:

????void?reverse(string&?s,int?start,int?end){

????????for(int?i=start,j=end;i<j;j--,i++){

????????????swap(s[i],s[j]);

????????}

????}

????void?quKongGe(string&?s){

????????int?slow=0;

????????for(int?fast=0;fast<s.size();fast++){

????????????if(s[fast]!='?'){

????????????????if(slow?!=?0)s[slow++]='?';

????????????????while(s[fast]!='?'?&&?fast<s.size()){

????????????????????s[slow++]=s[fast++];

????????????????}

????????????}

????????}

????????s.resize(slow);

????}

????string?reverseWords(string?s)?{

????????quKongGe(s);

????????reverse(s,0,s.size()-1);

????????int?start?=?0;

????????for(int?i=0;i<=s.size();i++){

????????????if(s[i]=='?'||i==s.size()){

????????????????reverse(s,start,i-1);

????????????????start?=?i+1;

????????????}

????????}

????????return?s;

????}

};