# 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. 整体翻转