翻轉(zhuǎn)字符串里的單詞

Given an input string, reverse the string word by word.

示例 1：

輸入: "the sky is blue"
輸出: "blue is sky the"

示例 2：

輸入: " hello world! "
輸出: "world! hello"
解釋: 輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。

示例 3：

輸入: "a good example"
輸出: "example good a"
解釋: 如果兩個(gè)單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)。

說(shuō)明：

• 無(wú)空格字符構(gòu)成一個(gè)單詞。

• 輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。

• 如果兩個(gè)單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)。

進(jìn)階：

請(qǐng)選用 C 語(yǔ)言的用戶嘗試使用 O(1) 額外空間復(fù)雜度的原地解法。

Note:

• A word is defined as a sequence of non-space characters.

• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.

• You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

解題思路：

Java 字符串不支持運(yùn)算符重載，無(wú)法用原地解法。 我們將字符串轉(zhuǎn)為字符型數(shù)組并用兩個(gè)指針來(lái)解這道題。指針 i 作為原字符串轉(zhuǎn)為字符數(shù)組的索引，從右向左移。指針 j 作為新字符數(shù)組索引，從左向右賦值得到原數(shù)組 count 長(zhǎng)度的字符。count記錄遇到的字母數(shù)量，每次遇到 空格 字符，新數(shù)組得到從該空格字符 向右 count 個(gè)字符并刷新count 計(jì)數(shù)。

Java：

class Solution {
 public String reverseWords(String s) {
 if (s.length()==0)return s;//如果為空直接返回
 char strs[]=s.toCharArray(),ans[]=new char[s.length()];//字符串轉(zhuǎn)為char字符數(shù)組
 int count=0,j=0;//全局變量j記錄新數(shù)組索引
 for(int i=s.length()-1;i>=0;i--){指針i從右向左遍歷strs字符
 if(strs[i]==' '){//判斷是否為空格字符
 int k=i+1;
 if(count>0){
 while (--count>=0){//從字符i向右count個(gè)字符賦給新數(shù)組ans
 ans[j++]=strs[k++];
 }
 ans[j++]=' ';
 count=0;//count初始化為0
 }
 }else if(i==0){
 for(;i<=count;i++)ans[j++]=strs[i];//左移到第一個(gè)字符時(shí)證明不是以空格開(kāi)頭，則從0獲取count+1個(gè)個(gè)字符賦給ans
 j+=1;
 break;
 }
 else {
 count++;//如果是字母，則count累加1
 }
 }
 if(j<1)return "";//如果j依然是0，則原字符串全為空格，返回空字符串
 String string=String.valueOf(ans,0,j-1);//char數(shù)組轉(zhuǎn)為字符串返回
 return string;
 }
}

為了考慮性能，轉(zhuǎn)成了多個(gè)判斷，所以有些繁瑣。最終運(yùn)行：Your runtime beats 99.91 % of java submissions

Python3：

python完全可以實(shí)現(xiàn)Java的思路，不再?gòu)?fù)現(xiàn)。這里利用函數(shù)投機(jī)取巧：

split() ，它可以把傳入字符串剔除空格后返回 所有單詞的數(shù)組

join() ，它可以指定一個(gè)數(shù)組以特定字符為間隔，拼接成一個(gè)字符串

加上 [::-1] 反轉(zhuǎn)數(shù)組，一行代碼既可實(shí)現(xiàn)該題目要求

’ abc def ’原字符串

[‘a(chǎn)bc’ , ‘def’]剔除空格返回String型單詞數(shù)組

[‘def’ , ‘a(chǎn)bc’]切片反轉(zhuǎn)數(shù)組

‘def abc’拼接成字符串

class Solution:
 def reverseWords(self, s: str) -> str:
 return " ".join(s.split()[::-1]) # 剔除所有空格字符返回?cái)?shù)組并反轉(zhuǎn)，以空格為間隔把數(shù)組拼成字符串