【題目描述】
Given an input string, reverse the string word by word.
給定一個字符串甥温,逐個翻轉(zhuǎn)字符串中的每個單詞锻煌。
【題目鏈接】
http://www.lintcode.com/en/problem/reverse-words-in-a-string/
【題目解析】
這道題讓我們翻轉(zhuǎn)字符串中的單詞,題目中給了我們寫特別說明姻蚓,如果單詞之間遇到多個空格宋梧,只能返回一個,而且首尾不能有單詞狰挡,并且對C語言程序員要求空間復雜度為O(1)捂龄,所以我們只能對原字符串s之間做修改,而不能聲明新的字符串加叁。那么我們?nèi)绾畏D(zhuǎn)字符串中的單詞呢倦沧,我們的做法是,先整個字符串整體翻轉(zhuǎn)一次殉农,然后再分別翻轉(zhuǎn)每一個單詞(或者先分別翻轉(zhuǎn)每一個單詞刀脏,然后再整個字符串整體翻轉(zhuǎn)一次)局荚,此時就能得到我們需要的結果了超凳。那么這里我們需要定義一些變量來輔助我們解題,storeIndex表示當前存儲到的位置耀态,n為字符串的長度轮傍。我們先給整個字符串反轉(zhuǎn)一下,然后我們開始循環(huán)首装,遇到空格直接跳過创夜,如果是非空格字符,我們此時看storeIndex是否為0仙逻,為0的話表示第一個單詞驰吓,不用增加空格涧尿;如果不為0,說明不是第一個單詞檬贰,需要在單詞中間加一個空格姑廉,然后我們要找到下一個單詞的結束位置我們用一個while循環(huán)來找下一個為空格的位置,在此過程中繼續(xù)覆蓋原字符串翁涤,找到結束位置了桥言,下面就來翻轉(zhuǎn)這個單詞,然后更新i為結尾位置葵礼,最后遍歷結束号阿,我們剪裁原字符串到storeIndex位置,就可以得到我們需要的結果
【參考答案】