# Reverse Words in a String ### Source - lintcode: [(53) Reverse Words in a String](http://www.lintcode.com/en/problem/reverse-words-in-a-string/) ~~~ Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". Example Clarification - What constitutes a word? A sequence of non-space characters constitutes a word. - Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces. - How about multiple spaces between two words? Reduce them to a single space in the reversed string. ~~~ ### 題解 1. 由第一個提問可知：題中只有空格字符和非空格字符之分，因此空格字符應為其一關鍵突破口。 1. 由第二個提問可知：輸入的前導空格或者尾隨空格在反轉后應去掉。 1. 由第三個提問可知：兩個單詞間的多個空格字符應合并為一個或刪除掉。 首先找到各個單詞(以空格隔開)，根據題目要求，單詞應從后往前依次放入。正向取出比較麻煩，因此可嘗試采用逆向思維——先將輸入字符串數組中的單詞從后往前逆序取出，取出單詞后即翻轉并append至新字符串數組。在append之前加入空格即可。 ### C++ ~~~ class Solution { public: /** * @param s : A string * @return : A string */ string reverseWords(string s) { if (s.empty()) { return s; } string s_ret, s_temp; string::size_type ix = s.size(); while (ix != 0) { s_temp.clear(); while (!isspace(s[--ix])) { s_temp.push_back(s[ix]); if (ix == 0) { break; } } if (!s_temp.empty()) { if (!s_ret.empty()) { s_ret.push_back(' '); } std::reverse(s_temp.begin(), s_temp.end()); s_ret.append(s_temp); } } return s_ret; } }; ~~~ ### 源碼分析 1. 首先處理異常，s為空時直接返回空。 1. 索引初始值`ix = s.size()`，而不是`ix = s.size() - 1`，便于處理`ix == 0`時的特殊情況。 1. 使用額外空間`s_ret, s_temp`，空間復雜度為O(n)，`s_temp`用于緩存臨時的單詞以append入`s_ret`。 1. 最后返回`s_ret`。 空間復雜度為O(1)的解法？ 1. 處理異常及特殊情況 1. 處理多個空格及首尾空格 1. 記住單詞的頭尾指針，翻轉之 1. 整體翻轉