题目地址：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/
题目描述
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
题目示例
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
解题思路
普通法：分析题目可得，分三个步骤处理字符串s；
- Step1：去除掉字符串s的首尾空格；
- Step2：从后向前遍历字符串s，并使用变量word_len统计每个单词字符数，如果遇到空字符并且word_len不为0，此时，检测到一个单词，向字符串res后面追加该单词以及空字符；
- Step3：处理字符串首部，即从字符串尾部遍历至首部i=0时，此时，不再需要追加空字符。
栈存储：观察题目示例，我们发现可以根据栈的特点“后进先出”，利用栈来解决问题。
- Step1：去除掉字符串s的首尾空格；
- Step2：定义栈word来存储字符串s中的所有单词，使用变量str存放当前单词；
- Step3：遍历字符串s中的字符s[i]，当该字符不是空字符时，将该字符加入到当前单词str中。否则，如果当前字符为空字符，且当前单词str大小不为0时，表示当前单词已完成拼接，则将该单词入栈，并重置存储临时单词变量str；
- Step4：遍历结束之后，判断当前单词str大小是否为0，如果不等于0，表示最后一个单词要存入栈中，此时，将最后一个单词入栈，到此，所有的单词均已成功入栈；
- Step5：当栈不为空时，对栈进行循环遍历，每次取出一个单词res，则追加一个空字符；
- Step6：将字符串res中最后多余的一个空字符去掉。
程序源码
普通法
class Solution { public: string reverseWords(string s) { if(s.size() < 1) return s; s.erase(0, s.find_first_not_of(' ')); s.erase(s.find_last_not_of(' ') + 1); string res; int word_len = 0; for(int i = s.length() - 1; i >= 0; i--) { if(s[i] !=' ') { word_len++; } else if(s[i] == ' ' && word_len != 0) { res += s.substr(i+1, word_len) + " "; word_len = 0; } if(i == 0 && word_len != 0) { res += s.substr(i, word_len); } }
return res;
}
};
栈存储
class Solution { public: string reverseWords(string s) { if(s.size() < 1) return s; s.erase(0, s.find_first_not_of(' ')); s.erase(s.find_last_not_of(' ') + 1); stack<string> word; string res, str; for(int i = 0 ; i < s.size(); i++) { if(s[i] != ' ') { str += s[i]; } else { if(str.size() != 0) { word.push(str); } str.clear(); //重置str用于存放新单词 } } if(str.size() != 0) //将字符串s的最后一个单词入栈 { word.push(str); } while(!word.empty()) { res += word.top() + " "; word.pop(); } res = res.substr(0,res.size() - 1); //去掉res中最后一个空字符，获得字符串s中从第0位开始的长度为res.size-1的字符串，即[0,res.size()-1) return res; } };